# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
153280 | 2019-09-13T07:38:22 Z | arnold518 | 곤돌라 (IOI14_gondola) | C++14 | 26 ms | 2404 KB |
#include "gondola.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const ll MOD = 1e9+9; int valid(int N, int *A) { int i, j; vector<int> S(A, A+N); sort(S.begin(), S.end()); S.erase(unique(S.begin(), S.end()), S.end()); if(S.size()!=N) return 0; int flag=-1; for(i=0; i<N; i++) { if(A[i]>N) continue; int t=(A[i]-1-i+N)%N; if(flag==-1) flag=t; else if(flag!=t) return 0; } return 1; } int replacement(int N, int *A, int *B) { int i, j, ret=0; int flag=0; vector<pii> V; for(i=0; i<N; i++) { if(A[i]<=N) { flag=(A[i]-1-i+N)%N; continue; } V.push_back({A[i], i}); } for(i=0; i<N; i++) A[i]=(i+flag)%N+1; sort(V.begin(), V.end()); int now=N+1; for(i=0; i<V.size(); i++) { int p=V[i].first, q=V[i].second; while(A[q]!=p) { B[ret++]=A[q]; A[q]=now++; } } return ret; } ll mypow(ll x, ll y) { if(y==0) return 1; if(y%2) return mypow(x, y-1)*x%MOD; ll ret=mypow(x, y/2); return ret*ret%MOD; } int countReplacement(int N, int *A) { int i, j; ll ans=1; if(!valid(N, A)) return 0; int flag=-1; vector<int> V; V.push_back(N); for(i=0; i<N; i++) { if(A[i]<=N) flag=0; else V.push_back(A[i]); } sort(V.begin(), V.end()); for(i=1; i<V.size(); i++) ans=ans*mypow(V.size()-i, V[i]-V[i-1]-1)%MOD; if(flag==-1) for(i=1; i<=N; i++) ans=ans*i%MOD; return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 348 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 360 KB | Output is correct |
2 | Correct | 2 ms | 424 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 | 376 KB | Output is correct |
6 | Correct | 10 ms | 888 KB | Output is correct |
7 | Correct | 21 ms | 1500 KB | Output is correct |
8 | Correct | 14 ms | 1272 KB | Output is correct |
9 | Correct | 7 ms | 632 KB | Output is correct |
10 | Correct | 20 ms | 1400 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 |
6 | Correct | 10 ms | 804 KB | Output is correct |
7 | Correct | 21 ms | 1528 KB | Output is correct |
8 | Correct | 14 ms | 1272 KB | Output is correct |
9 | Correct | 7 ms | 632 KB | Output is correct |
10 | Correct | 21 ms | 1532 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 10 ms | 764 KB | Output is correct |
14 | Correct | 2 ms | 400 KB | Output is correct |
15 | Correct | 21 ms | 1528 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 2 ms | 424 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 256 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 380 KB | Output is correct |
10 | Correct | 3 ms | 348 KB | Output is correct |
11 | Correct | 12 ms | 1136 KB | Output is correct |
12 | Correct | 14 ms | 1144 KB | Output is correct |
13 | Correct | 18 ms | 1532 KB | Output is correct |
14 | Correct | 12 ms | 1116 KB | Output is correct |
15 | Correct | 23 ms | 2404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 380 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 252 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 380 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 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 | 2 ms | 280 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 3 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 | 376 KB | Output is correct |
9 | Correct | 25 ms | 1612 KB | Output is correct |
10 | Correct | 20 ms | 1404 KB | Output is correct |
11 | Correct | 9 ms | 760 KB | Output is correct |
12 | Correct | 11 ms | 888 KB | Output is correct |
13 | Incorrect | 4 ms | 376 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 380 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 | 380 KB | Output is correct |
9 | Correct | 26 ms | 1612 KB | Output is correct |
10 | Correct | 21 ms | 1400 KB | Output is correct |
11 | Correct | 10 ms | 760 KB | Output is correct |
12 | Correct | 11 ms | 888 KB | Output is correct |
13 | Incorrect | 4 ms | 376 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |