# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
239514 | 2020-06-16T04:59:47 Z | Autoratch | Gondola (IOI14_gondola) | C++14 | 46 ms | 4856 KB |
#include "gondola.h" #include <bits/stdc++.h> using namespace std; const int N = 3e5 + 1; const int MOD = 1e9 + 9; int repl[N]; set<int> s; int valid(int n,int a[]) { int x,y = 0; for(int i = 0;i < n;i++) s.insert(a[i]); if(s.size()<n) return 0; for(int i = 0;i < n;i++) if(a[i]<=n) x = i,y = a[i]; if(y==0) return 1; for(int i = 0;i < n;i++) if(a[i]<=n) { int z = y+i-x; if(z>n) z%=n; if(z<1) z+=n; if(z!=a[i]) return 0; } return 1; } int replacement(int n,int a[],int ans[]) { int x,y = 0,mx = 0; for(int i = 0;i < n;i++) { if(a[i]<=n) x = i,y = a[i]; mx = max(mx,a[i]); } int ret = mx-n; int bx = mx; for(int i = 0;i < n;i++) { int z = y+i-x; if(z>n) z%=n; if(z<1) z+=n; if(z!=a[i]) repl[a[i]] = z; } for(int i = 0;i < ret;i++) { int j = i+n+1; if(!repl[j]) repl[j] = repl[bx],repl[bx] = j; ans[i] = repl[j]; } return ret; } int countReplacement(int n,int a[]) { int x,y = 0,mx = 0; for(int i = 0;i < n;i++) { if(a[i]<=n) x = i,y = a[i]; mx = max(mx,a[i]); s.insert(a[i]); } if(s.size()<n) return 0; for(int i = 0;i < n;i++) { int z = y+i-x; if(z>n) z%=n; if(z<1) z+=n; if(z!=a[i] and a[i]<=n) return 0; if(z!=a[i]) repl[a[i]] = z; } int s = 0,t = 0; for(int i = n+1;i <= mx;i++) if(!repl[i]) s++; else t++; long long res = 1; while(s--) res = (res*t)%MOD; int ans = res; return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 15 ms | 2176 KB | Output is correct |
7 | Correct | 33 ms | 3704 KB | Output is correct |
8 | Correct | 26 ms | 3968 KB | Output is correct |
9 | Correct | 11 ms | 1536 KB | Output is correct |
10 | Correct | 30 ms | 4600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
6 | Correct | 17 ms | 2288 KB | Output is correct |
7 | Correct | 35 ms | 3704 KB | Output is correct |
8 | Correct | 26 ms | 3968 KB | Output is correct |
9 | Correct | 11 ms | 1536 KB | Output is correct |
10 | Correct | 29 ms | 4608 KB | Output is correct |
11 | Correct | 4 ms | 384 KB | Output is correct |
12 | Correct | 4 ms | 256 KB | Output is correct |
13 | Correct | 19 ms | 2176 KB | Output is correct |
14 | Correct | 5 ms | 256 KB | Output is correct |
15 | Correct | 46 ms | 4856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Incorrect | 5 ms | 384 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Incorrect | 5 ms | 384 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 256 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Incorrect | 5 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 256 KB | Output is correct |
5 | Incorrect | 4 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 256 KB | Output is correct |
5 | Incorrect | 5 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |