# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
162041 | 2019-11-06T05:41:08 Z | oolimry | Gondola (IOI14_gondola) | C++14 | 1000 ms | 5368 KB |
#include "gondola.h" #include <bits/stdc++.h> using namespace std; long long mod = 1000000009; int valid(int n, int arr[]) { set<int> sset; for(int i = 0;i < n;i++){ sset.insert(arr[i]); } if(sset.size() != n) return 0; int anchor = -1; for(int i = 0;i < n;i++){ if(arr[i] <= n){ anchor = (arr[i] - i + n) % n; break; } } if(anchor == -1) return 1; for(int i = 0;i < n;i++){ if(arr[i] <= n){ if(arr[i] % n != (anchor + i) % n){ return 0; } } } return 1; } int replacement(int n, int arr[], int replacementSeq[]) { int anchor = 0; int ori[n]; map<int,int> m; set<int> s; for(int i = 0;i < n;i++){ if(arr[i] <= n){ anchor = (arr[i] - i + n) % n; break; } } int maxv = 0; int maxpos = 0; for(int i = 0;i < n;i++){ ori[i] = (anchor+i) % n; if(ori[i] == 0) ori[i] = n; if(arr[i] > maxv){ maxv = arr[i]; maxpos = i; } if(arr[i] > n){ m[arr[i]] = i; } } int cnt = 0; for(int r = n+1;r <= maxv;r++){ int rindex = 0; if(m.find(r) == m.end()){ rindex = maxpos; } else{ rindex = m[r]; } replacementSeq[cnt] = ori[rindex]; ori[rindex] = r; cnt++; } return cnt; } int countReplacement(int n, int arr[]) { if(!valid(n,arr)) return 0; long long ans = 1; int maxv = 0; int freee = n; set<int> s; bool has = true; for(int i = 0;i < n;i++){ maxv = max(maxv, arr[i]); if(arr[i] <= n){ freee--; has = false; } else{ s.insert(arr[i]); } } for(int r = n+1;r <= maxv;r++){ if(s.find(r) != s.end()){ freee--; } else{ ans *= freee; ans %= mod; } } if(has){ ans *= n; ans %= mod; } return ans; }
Compilation message
# | 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 | 376 KB | Output is correct |
5 | 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 | 376 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 | 16 ms | 2168 KB | Output is correct |
7 | Correct | 39 ms | 3704 KB | Output is correct |
8 | Correct | 29 ms | 3960 KB | Output is correct |
9 | Correct | 10 ms | 1528 KB | Output is correct |
10 | Correct | 36 ms | 4600 KB | Output is 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 | 6 ms | 256 KB | Output is correct |
6 | Correct | 16 ms | 2296 KB | Output is correct |
7 | Correct | 39 ms | 3684 KB | Output is correct |
8 | Correct | 29 ms | 3960 KB | Output is correct |
9 | Correct | 10 ms | 1516 KB | Output is correct |
10 | Correct | 38 ms | 4640 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 21 ms | 2168 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 51 ms | 4700 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 | 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 | 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 |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 380 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 | 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 | 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 | 376 KB | Output is correct |
11 | Correct | 12 ms | 888 KB | Output is correct |
12 | Correct | 15 ms | 1016 KB | Output is correct |
13 | Correct | 35 ms | 2752 KB | Output is correct |
14 | Correct | 12 ms | 888 KB | Output is correct |
15 | Correct | 36 ms | 3064 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 320 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 | 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 | 504 KB | Output is 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 | 256 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 | 256 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 85 ms | 4600 KB | Output is correct |
10 | Correct | 59 ms | 3832 KB | Output is correct |
11 | Correct | 28 ms | 1656 KB | Output is correct |
12 | Correct | 29 ms | 1912 KB | Output is correct |
13 | Correct | 12 ms | 680 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 | 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 | 504 KB | Output is correct |
9 | Correct | 79 ms | 4600 KB | Output is correct |
10 | Correct | 60 ms | 3832 KB | Output is correct |
11 | Correct | 28 ms | 1656 KB | Output is correct |
12 | Correct | 30 ms | 1912 KB | Output is correct |
13 | Correct | 11 ms | 632 KB | Output is correct |
14 | Execution timed out | 1071 ms | 5368 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |