# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
209588 | 2020-03-14T18:06:17 Z | Lukoloz | 곤돌라 (IOI14_gondola) | C++14 | 141 ms | 12408 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[]){ map <int,bool> fl; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 63 ms | 12024 KB | Output is correct |
2 | Correct | 63 ms | 12024 KB | Output is correct |
3 | Correct | 62 ms | 12024 KB | Output is correct |
4 | Correct | 64 ms | 12024 KB | Output is correct |
5 | Correct | 63 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 11896 KB | Output is correct |
2 | Correct | 62 ms | 12028 KB | Output is correct |
3 | Correct | 63 ms | 12024 KB | Output is correct |
4 | Correct | 62 ms | 12024 KB | Output is correct |
5 | Correct | 63 ms | 12024 KB | Output is correct |
6 | Correct | 82 ms | 12152 KB | Output is correct |
7 | Correct | 76 ms | 12408 KB | Output is correct |
8 | Correct | 87 ms | 12408 KB | Output is correct |
9 | Correct | 69 ms | 12152 KB | Output is correct |
10 | Correct | 92 ms | 12408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 63 ms | 12024 KB | Output is correct |
2 | Correct | 63 ms | 12024 KB | Output is correct |
3 | Correct | 63 ms | 12024 KB | Output is correct |
4 | Correct | 63 ms | 12024 KB | Output is correct |
5 | Correct | 62 ms | 12024 KB | Output is correct |
6 | Correct | 75 ms | 12180 KB | Output is correct |
7 | Correct | 75 ms | 12408 KB | Output is correct |
8 | Correct | 86 ms | 12284 KB | Output is correct |
9 | Correct | 71 ms | 12152 KB | Output is correct |
10 | Correct | 91 ms | 12408 KB | Output is correct |
11 | Correct | 63 ms | 12024 KB | Output is correct |
12 | Correct | 64 ms | 12024 KB | Output is correct |
13 | Correct | 69 ms | 12152 KB | Output is correct |
14 | Correct | 62 ms | 12024 KB | Output is correct |
15 | Correct | 76 ms | 12408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 380 KB | Output is correct |
5 | Correct | 5 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
6 | Correct | 5 ms | 376 KB | Output is correct |
7 | Correct | 5 ms | 376 KB | Output is correct |
8 | Correct | 6 ms | 376 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 380 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 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 | 376 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 |
11 | Correct | 15 ms | 632 KB | Output is correct |
12 | Correct | 16 ms | 632 KB | Output is correct |
13 | Correct | 18 ms | 1144 KB | Output is correct |
14 | Correct | 17 ms | 632 KB | Output is correct |
15 | Correct | 24 ms | 2168 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 12024 KB | Output is correct |
2 | Correct | 65 ms | 12024 KB | Output is correct |
3 | Correct | 63 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 12024 KB | Output is correct |
2 | Correct | 63 ms | 12024 KB | Output is correct |
3 | Correct | 64 ms | 12024 KB | Output is correct |
4 | Correct | 69 ms | 12092 KB | Output is correct |
5 | Correct | 64 ms | 12024 KB | Output is correct |
6 | Correct | 67 ms | 12024 KB | Output is correct |
7 | Correct | 63 ms | 12024 KB | Output is correct |
8 | Correct | 62 ms | 12024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 63 ms | 12024 KB | Output is correct |
2 | Correct | 64 ms | 12028 KB | Output is correct |
3 | Correct | 63 ms | 12024 KB | Output is correct |
4 | Correct | 66 ms | 12040 KB | Output is correct |
5 | Correct | 63 ms | 12024 KB | Output is correct |
6 | Correct | 63 ms | 12024 KB | Output is correct |
7 | Correct | 64 ms | 12024 KB | Output is correct |
8 | Correct | 62 ms | 12024 KB | Output is correct |
9 | Correct | 141 ms | 12280 KB | Output is correct |
10 | Correct | 104 ms | 12280 KB | Output is correct |
11 | Correct | 80 ms | 12156 KB | Output is correct |
12 | Correct | 83 ms | 12152 KB | Output is correct |
13 | Incorrect | 67 ms | 12024 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 12024 KB | Output is correct |
2 | Correct | 64 ms | 12024 KB | Output is correct |
3 | Correct | 64 ms | 12024 KB | Output is correct |
4 | Correct | 62 ms | 12024 KB | Output is correct |
5 | Correct | 63 ms | 12024 KB | Output is correct |
6 | Correct | 67 ms | 12160 KB | Output is correct |
7 | Correct | 62 ms | 12024 KB | Output is correct |
8 | Correct | 64 ms | 12024 KB | Output is correct |
9 | Correct | 117 ms | 12280 KB | Output is correct |
10 | Correct | 102 ms | 12280 KB | Output is correct |
11 | Correct | 79 ms | 12152 KB | Output is correct |
12 | Correct | 82 ms | 12152 KB | Output is correct |
13 | Incorrect | 67 ms | 12024 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |