Submission #946027
Source Code Expand
import java.util.*; import java.io.*; public class Main { long mod = 1000000007; int MAX = 600000; long[] fact = new long[MAX]; void precalc() { fact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = fact[i - 1] * i % mod; } } class BIT { int[] tree; public BIT(int n) { tree = new int[n]; } int get(int pos) { int res = 0; while (pos >= 0) { res += tree[pos]; pos = (pos & (pos + 1)) - 1; } return res; } void add(int pos, int val) { while (pos < tree.length) { tree[pos] += val; pos |= pos + 1; } } } void solve() { precalc(); int n = in.nextInt(); int[] p = new int[n]; TreeSet<Integer> free = new TreeSet<>(); for (int i = 0; i < n; i++) { free.add(i); } for (int i = 0; i < n; i++) { p[i] = in.nextInt() - 1; free.remove(p[i]); } int[] all = new int[free.size()]; int numFree = 0; for (int i : free) { all[numFree++] = i; } long result = 0; BIT tree = new BIT(n); long sumEmpty = 0; int tmp = 0; for (int i = n - 1; i >= 0; i--) { if (p[i] == -1) { sumEmpty = (sumEmpty + fact[n - i - 1] * tmp) % mod; tmp++; } } if (numFree >= 2) { result = 1L * numFree * (numFree - 1) / 2 % mod * sumEmpty % mod * fact[numFree - 2] % mod; } int freePlaces = 0; for (int i = n - 1; i >= 0; i--) { if (p[i] != -1) { int cnt = tree.get(p[i]); { long add = 1L * cnt * fact[n - i - 1] % mod * fact[numFree] % mod; result = (result + add) % mod; } if (numFree > 0) { long add = 1L * findLess(all, p[i]) * freePlaces % mod * fact[n - i - 1] % mod * fact[numFree - 1] % mod; result = (result + add) % mod; } tree.add(p[i], 1); } else { freePlaces++; } } Arrays.fill(tree.tree, 0); freePlaces = 0; long sumFacts = 0; for (int i = 0; i < n; i++) { if (p[i] == -1) { freePlaces++; sumFacts = (sumFacts + fact[n - i - 1]) % mod; continue; } if (numFree > 0) { long add = 1L * (numFree - findLess(all, p[i])) * sumFacts % mod * fact[numFree - 1] % mod; result = (result + add) % mod; } } out.println((result + fact[numFree]) % mod); } int findLess(int[] a, int i) { int pos = Arrays.binarySearch(a, i); return -pos - 1; } FastScanner in; PrintWriter out; void run() { in = new FastScanner(); out = new PrintWriter(System.out); solve(); out.close(); } class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } public FastScanner(String s) { try { br = new BufferedReader(new FileReader(s)); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } public String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { } } return st.nextToken(); } public int nextInt() { return Integer.parseInt(nextToken()); } public long nextLong() { return Long.parseLong(nextToken()); } public double nextDouble() { return Double.parseDouble(nextToken()); } } public static void main(String[] args) { new Main().run(); } }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | VArtem |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1200 |
Code Size | 3443 Byte |
Status | AC |
Exec Time | 1256 ms |
Memory | 92796 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | 700 / 700 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt |
Subtask | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt, 2_051.txt, 2_052.txt, 2_053.txt, 2_054.txt, 2_055.txt, 2_056.txt, 2_057.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 135 ms | 13392 KB |
0_001.txt | AC | 128 ms | 13140 KB |
0_002.txt | AC | 127 ms | 13136 KB |
0_003.txt | AC | 117 ms | 13140 KB |
0_004.txt | AC | 117 ms | 13140 KB |
1_005.txt | AC | 119 ms | 13264 KB |
1_006.txt | AC | 115 ms | 13132 KB |
1_007.txt | AC | 118 ms | 13260 KB |
1_008.txt | AC | 149 ms | 15172 KB |
1_009.txt | AC | 136 ms | 14288 KB |
1_010.txt | AC | 154 ms | 15060 KB |
1_011.txt | AC | 153 ms | 14644 KB |
1_012.txt | AC | 150 ms | 15172 KB |
1_013.txt | AC | 132 ms | 14288 KB |
1_014.txt | AC | 167 ms | 15332 KB |
1_015.txt | AC | 145 ms | 14980 KB |
1_016.txt | AC | 155 ms | 15300 KB |
1_017.txt | AC | 115 ms | 13264 KB |
1_018.txt | AC | 157 ms | 15236 KB |
1_019.txt | AC | 157 ms | 15104 KB |
1_020.txt | AC | 157 ms | 15620 KB |
1_021.txt | AC | 138 ms | 14676 KB |
1_022.txt | AC | 157 ms | 15744 KB |
1_023.txt | AC | 151 ms | 15492 KB |
1_024.txt | AC | 156 ms | 15300 KB |
1_025.txt | AC | 120 ms | 13136 KB |
1_026.txt | AC | 165 ms | 15304 KB |
1_027.txt | AC | 155 ms | 15236 KB |
1_028.txt | AC | 156 ms | 15428 KB |
1_029.txt | AC | 168 ms | 15428 KB |
1_030.txt | AC | 154 ms | 15172 KB |
1_031.txt | AC | 157 ms | 15184 KB |
1_032.txt | AC | 153 ms | 15184 KB |
2_033.txt | AC | 859 ms | 79464 KB |
2_034.txt | AC | 401 ms | 49416 KB |
2_035.txt | AC | 933 ms | 81788 KB |
2_036.txt | AC | 1096 ms | 79384 KB |
2_037.txt | AC | 1034 ms | 86596 KB |
2_038.txt | AC | 968 ms | 82320 KB |
2_039.txt | AC | 1036 ms | 82400 KB |
2_040.txt | AC | 521 ms | 49632 KB |
2_041.txt | AC | 1100 ms | 87156 KB |
2_042.txt | AC | 330 ms | 36556 KB |
2_043.txt | AC | 1145 ms | 89424 KB |
2_044.txt | AC | 642 ms | 65800 KB |
2_045.txt | AC | 1206 ms | 85616 KB |
2_046.txt | AC | 1180 ms | 83884 KB |
2_047.txt | AC | 1236 ms | 85596 KB |
2_048.txt | AC | 576 ms | 49692 KB |
2_049.txt | AC | 1256 ms | 86268 KB |
2_050.txt | AC | 724 ms | 73980 KB |
2_051.txt | AC | 1126 ms | 92796 KB |
2_052.txt | AC | 1127 ms | 83984 KB |
2_053.txt | AC | 846 ms | 82564 KB |
2_054.txt | AC | 1216 ms | 86640 KB |
2_055.txt | AC | 1066 ms | 87128 KB |
2_056.txt | AC | 940 ms | 84436 KB |
2_057.txt | AC | 986 ms | 85220 KB |