# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
159955 | 2019-10-25T14:20:11 Z | rama_pang | 곤돌라 (IOI14_gondola) | C++14 | 54 ms | 4984 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]; pivot--; for (int i = 0; i < n + n && pivot >= 0; 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]; pivot--; for (int i = 0; i < n + n && pivot >= 0; 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
# | 결과 | 실행 시간 | 메모리 | 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 | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 252 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 | 19 ms | 2444 KB | Output is correct |
7 | Correct | 15 ms | 1016 KB | Output is correct |
8 | Correct | 33 ms | 4216 KB | Output is correct |
9 | Correct | 10 ms | 1528 KB | Output is correct |
10 | Correct | 40 ms | 4984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 17 ms | 2424 KB | Output is correct |
7 | Correct | 15 ms | 1016 KB | Output is correct |
8 | Correct | 33 ms | 4216 KB | Output is correct |
9 | Correct | 12 ms | 1528 KB | Output is correct |
10 | Correct | 39 ms | 4856 KB | Output is correct |
11 | Correct | 2 ms | 380 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 8 ms | 636 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 16 ms | 984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 380 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 0 ms | 380 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 | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 552 KB | Output is correct |
11 | Correct | 13 ms | 976 KB | Output is correct |
12 | Correct | 14 ms | 1016 KB | Output is correct |
13 | Correct | 19 ms | 1528 KB | Output is correct |
14 | Correct | 13 ms | 1396 KB | Output is correct |
15 | Correct | 25 ms | 2496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 376 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 52 ms | 4856 KB | Output is correct |
10 | Correct | 42 ms | 4160 KB | Output is correct |
11 | Correct | 16 ms | 1656 KB | Output is correct |
12 | Correct | 21 ms | 2040 KB | Output is correct |
13 | Incorrect | 6 ms | 724 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 256 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 54 ms | 4856 KB | Output is correct |
10 | Correct | 42 ms | 4088 KB | Output is correct |
11 | Correct | 16 ms | 1656 KB | Output is correct |
12 | Correct | 20 ms | 2040 KB | Output is correct |
13 | Incorrect | 6 ms | 760 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |