# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
209586 | 2020-03-14T18:03:56 Z | Lukoloz | Gondola (IOI14_gondola) | C++14 | 24 ms | 2164 KB |
#include <bits/stdc++.h> #include "gondola.h" #define ll long long #define ff first #define ss second #define pb push_back #define MAXN 100005 #define NASH 1000000009LL using namespace std; ll pow(ll i, ll j){ if (j==0) return 1; if (j==1) return i; ll ret=pow(i,j/2); ret=(ret*ret)%NASH; if (j%2) ret=(ret*i)%NASH; return ret; } int valid(int n, int inputSeq[]){ bool fl[250005]; int tdif,dif=-1; for (int i=0; i<250005; i++) fl[i]=0; for (int i=0; i<n; i++){ if (fl[inputSeq[i]]) return 0; fl[inputSeq[i]]=1; if (inputSeq[i]<=n){ tdif=inputSeq[i]-1-i; if (tdif<0) tdif+=n; if (dif!=-1 && tdif!=dif) return 0; dif=tdif; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int dif=0,mx=0,mxi; for (int i=0; i<n; i++){ if (gondolaSeq[i]>mx){ mx=gondolaSeq[i]; mxi=i; } if (gondolaSeq[i]<=n){ dif=gondolaSeq[i]-1-i; if (dif<0) dif+=n; } } for (int i=0; i<mx-n; i++) replacementSeq[i]=0; for (int i=0; i<n; i++){ if (i==mxi || gondolaSeq[i]<=n) continue; replacementSeq[gondolaSeq[i]-n-1]=(i+dif)%n+1; } mxi=(mxi+dif)%n+1; for (int i=0; i<mx-n; i++){ if (replacementSeq[i]!=0) continue; replacementSeq[i]=mxi; mxi=i+n+1; } // for (int i=0; i<mx-n; i++) cout<<replacementSeq[i]<<" "; cout<<endl; return mx-n; } int countReplacement(int n, int inputSeq[]){ if (!valid(n,inputSeq)) return 0; ll ans=1; vector <int> v; v.pb(n); for (int i=0; i<n; i++) if (inputSeq[i]>n) v.pb(inputSeq[i]); sort(v.begin(),v.end()); for (int i=1; i<v.size(); i++){ ans=(ans*pow((ll)v.size()-i,(ll)(v[i]-v[i-1]-(ll)(v.size()!=n+1))))%NASH; } return (int)ans; } // int main(){ // int n; // cin>>n; // int arr[n]; // for (int i=0; i<n; i++) cin>>arr[i]; // cout<<countReplacement(n,arr)<<endl; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 636 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 508 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 10 ms | 632 KB | Output is correct |
7 | Correct | 16 ms | 888 KB | Output is correct |
8 | Correct | 15 ms | 888 KB | Output is correct |
9 | Correct | 8 ms | 632 KB | Output is correct |
10 | Correct | 16 ms | 888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 10 ms | 760 KB | Output is correct |
7 | Correct | 16 ms | 888 KB | Output is correct |
8 | Correct | 14 ms | 888 KB | Output is correct |
9 | Correct | 8 ms | 632 KB | Output is correct |
10 | Correct | 15 ms | 888 KB | Output is correct |
11 | Correct | 5 ms | 632 KB | Output is correct |
12 | Correct | 5 ms | 504 KB | Output is correct |
13 | Correct | 10 ms | 632 KB | Output is correct |
14 | Correct | 5 ms | 632 KB | Output is correct |
15 | Correct | 16 ms | 888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 4 ms | 128 KB | Output is correct |
5 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 256 KB | Output is correct |
5 | Correct | 5 ms | 376 KB | Output is correct |
6 | Correct | 5 ms | 376 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 5 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 376 KB | Output is correct |
4 | Correct | 4 ms | 376 KB | Output is correct |
5 | Correct | 5 ms | 256 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 5 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 6 ms | 376 KB | Output is correct |
11 | Correct | 14 ms | 632 KB | Output is correct |
12 | Correct | 16 ms | 760 KB | Output is correct |
13 | Correct | 17 ms | 1144 KB | Output is correct |
14 | Correct | 14 ms | 632 KB | Output is correct |
15 | Correct | 24 ms | 2164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 508 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
7 | Correct | 5 ms | 504 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 632 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
7 | Correct | 5 ms | 504 KB | Output is correct |
8 | Correct | 5 ms | 632 KB | Output is correct |
9 | Correct | 21 ms | 1272 KB | Output is correct |
10 | Correct | 19 ms | 1144 KB | Output is correct |
11 | Correct | 10 ms | 888 KB | Output is correct |
12 | Correct | 11 ms | 888 KB | Output is correct |
13 | Incorrect | 6 ms | 632 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 504 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 504 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 504 KB | Output is correct |
7 | Correct | 5 ms | 504 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
9 | Correct | 22 ms | 1272 KB | Output is correct |
10 | Correct | 18 ms | 1272 KB | Output is correct |
11 | Correct | 10 ms | 888 KB | Output is correct |
12 | Correct | 11 ms | 888 KB | Output is correct |
13 | Incorrect | 6 ms | 632 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |