# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
128335 | 2019-07-10T18:10:28 Z | dolphingarlic | Gondola (IOI14_gondola) | C++14 | 26 ms | 2272 KB |
#include "gondola.h" #include <bits/stdc++.h> #pragma GCC Optimize("O3") #define FOR(i, x, y) for (int i = x; i < y; i++) #define MOD 1000000009 typedef long long ll; using namespace std; int valid(int n, int inputSeq[]) { vector<int> gondolas; FOR(i, 0, n) gondolas.push_back(inputSeq[i]); sort(gondolas.begin(), gondolas.end()); FOR(i, 1, n) if (gondolas[i] == gondolas[i - 1]) return 0; FOR(i, 0, n) { if (inputSeq[i] <= n) { FOR(j, 1, n + 1) { int k = (i + j - inputSeq[i]) % n; while (k < 0) k += n; if (inputSeq[k] <= n && inputSeq[k] != j) return 0; } return 1; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<pair<int, int>> broken; int offset = 0; FOR(i, 0, n) { if (gondolaSeq[i] > n) broken.push_back({gondolaSeq[i], i + 1}); else offset = i - gondolaSeq[i] + 1; } FOR(i, 0, broken.size()) { broken[i].second = (broken[i].second - offset - 1 + n) % n + 1; } int indx = 0, curr = n; sort(broken.begin(), broken.end()); for (pair<int, int> i : broken) { replacementSeq[indx++] = i.second; curr++; FOR(j, curr, i.first) replacementSeq[indx++] = j; curr = i.first; } return indx; } //---------------------- ll expo(ll x, ll y) { ll res = 1; x = x % MOD; while (y > 0) { if (y & 1) res = (res * x) % MOD; y = y >> 1; x = (x * x) % MOD; } return res; } int countReplacement(int n, int inputSeq[]) { if (!valid(n, inputSeq)) return 0; // If there are k replaced cars {a, b}, {c, d}, ... // Then ans is k^(d - b) * (k - 1)^(f - d) + ... vector<ll> broken; broken.push_back(0); FOR(i, 0, n) { if (inputSeq[i] > n) broken.push_back((ll) (inputSeq[i] - n)); } sort(broken.begin(), broken.end()); ll ans = 1; FOR(i, 1, broken.size()) { ans = (ans * expo(broken.size() - i, (broken[i] - broken[i - 1] - 1) % (MOD - 1))) % MOD; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 276 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 10 ms | 888 KB | Output is correct |
7 | Correct | 22 ms | 1268 KB | Output is correct |
8 | Correct | 15 ms | 1268 KB | Output is correct |
9 | Correct | 18 ms | 632 KB | Output is correct |
10 | Correct | 23 ms | 1268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 12 ms | 888 KB | Output is correct |
7 | Correct | 22 ms | 1264 KB | Output is correct |
8 | Correct | 15 ms | 1268 KB | Output is correct |
9 | Correct | 7 ms | 632 KB | Output is correct |
10 | Correct | 20 ms | 1268 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 10 ms | 888 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 22 ms | 1396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 504 KB | Output is correct |
11 | Correct | 11 ms | 632 KB | Output is correct |
12 | Correct | 13 ms | 632 KB | Output is correct |
13 | Correct | 18 ms | 1276 KB | Output is correct |
14 | Correct | 11 ms | 632 KB | Output is correct |
15 | Correct | 19 ms | 2272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 424 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 26 ms | 1604 KB | Output is correct |
10 | Correct | 21 ms | 1400 KB | Output is correct |
11 | Correct | 4 ms | 788 KB | Output is correct |
12 | Correct | 12 ms | 764 KB | Output is correct |
13 | Incorrect | 5 ms | 504 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 452 KB | Output is correct |
8 | Correct | 2 ms | 380 KB | Output is correct |
9 | Correct | 26 ms | 1604 KB | Output is correct |
10 | Correct | 23 ms | 1400 KB | Output is correct |
11 | Correct | 10 ms | 788 KB | Output is correct |
12 | Correct | 13 ms | 896 KB | Output is correct |
13 | Incorrect | 2 ms | 504 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |