# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
159950 | 2019-10-25T14:10:34 Z | rama_pang | Gondola (IOI14_gondola) | C++14 | 48 ms | 4860 KB |
#include "gondola.h" #include <bits/stdc++.h> using namespace std; int valid(int n, int inputSeq[]) { deque<int> gondola(n); for (int i = 0; i < n; i++) gondola[i] = inputSeq[i]; int pivot = -1; for (int i = 0; i < n; i++) if (gondola[i] <= n) pivot = gondola[i]; for (int i = 0; i < n + n && pivot != -1; i++) { if (gondola[pivot] == pivot + 1) break; gondola.push_back(gondola.front()); gondola.pop_front(); } for (int i = 0; i < n; i++) if (gondola[i] != i + 1 && gondola[i] <= n) return 0; map<int, int> cnt; for (int i = 0; i < n; i++) cnt[gondola[i]]++; for (auto i : cnt) if (i.second > 1) return 0; return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { deque<int> gondola(n); for (int i = 0; i < n; i++) gondola[i] = gondolaSeq[i]; int pivot = -1; for (int i = 0; i < n; i++) if (gondola[i] <= n) pivot = gondola[i]; for (int i = 0; i < n + n && pivot != -1; i++) { if (gondola[pivot] == pivot + 1) break; gondola.push_back(gondola.front()); gondola.pop_front(); } vector<pair<int, int>> replace; vector<int> ans; for (int i = 0; i < n; i++) if (gondola[i] > n) replace.emplace_back(gondola[i], i + 1); sort(replace.begin(), replace.end()); int cur = n + 1; for (int i = 0; i < replace.size(); i++) { ans.push_back(replace[i].second); for (int j = cur; j < replace[i].first; j++) { ans.push_back(j); } cur = replace[i].first + 1; } for (int i = 0; i < ans.size(); i++) replacementSeq[i] = ans[i]; return ans.size(); } using lint = long long; const lint MOD = 1e9 + 9; lint pw(lint n, lint x) { if (x == 0) return 1; if (x == 1) return n; lint res = pw(n, x / 2); res %= MOD; res *= res; res %= MOD; if (x & 1) res *= n; res %= MOD; return res; } int countReplacement(int n, int inputSeq[]) { if (valid(n, inputSeq) == 0) return 0; deque<int> gondola(n); for (int i = 0; i < n; i++) gondola[i] = inputSeq[i]; vector<int> replace; for (int i = 0; i < n; i++) if (gondola[i] > n) replace.emplace_back(gondola[i]); sort(replace.begin(), replace.end()); lint active = replace.size(); lint cur = n + 1; lint res = 1; for (int i = 0; i < replace.size(); i++) { res *= pw(active, replace[i] - cur); cur = replace[i] + 1; active--; res %= MOD; } return (int)res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 128 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 252 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 |
6 | Correct | 19 ms | 2424 KB | Output is correct |
7 | Correct | 18 ms | 1016 KB | Output is correct |
8 | Correct | 32 ms | 4216 KB | Output is correct |
9 | Correct | 13 ms | 1528 KB | Output is correct |
10 | Correct | 47 ms | 4856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 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 | 21 ms | 2424 KB | Output is correct |
7 | Correct | 18 ms | 1016 KB | Output is correct |
8 | Correct | 38 ms | 4216 KB | Output is correct |
9 | Correct | 11 ms | 1528 KB | Output is correct |
10 | Correct | 48 ms | 4860 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 6 ms | 888 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 19 ms | 1528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 252 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 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 | 3 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 504 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 | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 16 ms | 888 KB | Output is correct |
12 | Correct | 17 ms | 1016 KB | Output is correct |
13 | Incorrect | 23 ms | 1528 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Incorrect | 2 ms | 376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Incorrect | 2 ms | 376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Incorrect | 2 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Incorrect | 2 ms | 380 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |