# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
119645 | 2019-06-21T14:38:41 Z | CaroLinda | 곤돌라 (IOI14_gondola) | C++14 | 87 ms | 6008 KB |
#include <bits/stdc++.h> #include "gondola.h" #define lp(i,a,b) for(int i=a;i<b;i++) #define ll long long #define pii pair<int,int> #define ff first #define ss second #define pb push_back const int MOD=1e9+9; const int maxn=1e5+10; using namespace std ; int valid(int n, int inputSeq[]) { set<int> s ; int k=-1 ; lp(i,0,n) { if( s.find(inputSeq[i]) != s.end() ) return 0 ; s.insert(inputSeq[i]) ; if(inputSeq[i]<=n) k = i ; } if(k==-1) return 1 ; int count=(inputSeq[k]-k-1+n)%n+1 ; lp(i,0,n) { if(inputSeq[i]<=n && inputSeq[i]!=count) return 0 ; if (++count>n) count=1 ; } return 1 ; } int replacement(int n, int gondolaSeq[] , int replacementSeq[]) { int k=-1; lp(i,0,n) if(gondolaSeq[i]<=n)k=i ; int count ; if(k==-1) count=1 ; else count = (gondolaSeq[k]-k-1+n)%n+1 ; vector<pii> p ; lp(i,0,n) { if(gondolaSeq[i]>n) p.pb( pii( gondolaSeq[i] , count ) ) ; if(++count>n) count=1 ; } sort(p.begin(),p.end()) ; int ind=0 ; lp(i,0,p.size()){ while(ind+n+1<=p[i].ff){ replacementSeq[ind]=p[i].ss ; p[i].ss = ind+n+1 ; ind++ ; } } return ind ; } ll expo(ll x, int n) { if(n==0) return 1 ; if(n==1) return x ; if(n%2==0) { ll aux=expo(x,n/2) ; return (aux*aux)%MOD ; } return (x*expo(x,n-1))%MOD ; } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq)) return 0 ; int g ; for(g=0;g<n;g++) if(inputSeq[g]>n) break ; if(g==n+1) return 1 ; ll ans = 1 ; vector<int> p ; p.pb(n+1) ; lp(i,0,n) if(inputSeq[i]>n) p.pb(inputSeq[i]) ; if(p.size() == n+1 ) ans = n ; sort(p.begin(),p.end()) ; lp(i,1,p.size()) { ans = (ans * expo(p.size() - i , p[i]-p[i-1] ) ) % MOD ; p[i] ++ ; } return ans ; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 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 | 3 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 15 ms | 2304 KB | Output is correct |
7 | Correct | 14 ms | 768 KB | Output is correct |
8 | Correct | 29 ms | 4088 KB | Output is correct |
9 | Correct | 10 ms | 1536 KB | Output is correct |
10 | Correct | 38 ms | 4600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 16 ms | 2304 KB | Output is correct |
7 | Correct | 12 ms | 768 KB | Output is correct |
8 | Correct | 29 ms | 4096 KB | Output is correct |
9 | Correct | 10 ms | 1536 KB | Output is correct |
10 | Correct | 37 ms | 4560 KB | Output is correct |
11 | Correct | 2 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
13 | Correct | 21 ms | 2176 KB | Output is correct |
14 | Correct | 2 ms | 256 KB | Output is correct |
15 | Correct | 58 ms | 4856 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 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 | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 384 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 | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 11 ms | 640 KB | Output is correct |
12 | Correct | 11 ms | 640 KB | Output is correct |
13 | Correct | 19 ms | 1296 KB | Output is correct |
14 | Correct | 10 ms | 640 KB | Output is correct |
15 | Correct | 20 ms | 2260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 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 | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 49 ms | 4472 KB | Output is correct |
10 | Correct | 43 ms | 3832 KB | Output is correct |
11 | Correct | 21 ms | 1524 KB | Output is correct |
12 | Correct | 18 ms | 1920 KB | Output is correct |
13 | Correct | 6 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 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 | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 48 ms | 4472 KB | Output is correct |
10 | Correct | 39 ms | 3968 KB | Output is correct |
11 | Correct | 18 ms | 1536 KB | Output is correct |
12 | Correct | 19 ms | 1900 KB | Output is correct |
13 | Correct | 5 ms | 768 KB | Output is correct |
14 | Correct | 63 ms | 5368 KB | Output is correct |
15 | Correct | 87 ms | 6008 KB | Output is correct |
16 | Correct | 12 ms | 1408 KB | Output is correct |
17 | Correct | 47 ms | 4216 KB | Output is correct |
18 | Correct | 24 ms | 2532 KB | Output is correct |