# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
160677 | 2019-10-29T09:51:55 Z | GioChkhaidze | 곤돌라 (IOI14_gondola) | C++14 | 31 ms | 2296 KB |
#include <bits/stdc++.h> #include "gondola.h" #define F first #define S second using namespace std; bool f[250003],F[250003]; int Gondol[250003]; pair < int , int > a[250003]; int valid(int n, int inputSeq[]) { int idx=-1; for (int i=0; i<n; i++) if (!f[inputSeq[i]]) f[inputSeq[i]]=1; else return 0; for (int i=0; i<n; i++) if (inputSeq[i]<=n) { idx=i; break; } if (idx==-1) return 1; int x=inputSeq[idx]; for (int i=idx+1; ; i++) { x++; if (x>n) x-=n; if (i==n) i-=n; if (i==idx) break; if (inputSeq[i]<=n && inputSeq[i]!=x) return 0; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int l=0,M=0,idx=-1; for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) { idx=i; break; } for (int i=0; i<n; i++) a[i].F=gondolaSeq[i],a[i].S=i; sort(a,a+n); if (idx==-1) { for (int i=0; i<n; i++) Gondol[i]=i+1; } else { int x=gondolaSeq[idx]; Gondol[idx]=x; for (int i=idx+1; ; i++) { x++; if (x>n) x-=n; if (i==n) i-=n; if (i==idx) break; Gondol[i]=x; } } int last=n; for (int i=0; i<n; i++) { if (a[i].F<=n) continue; int id=a[i].S; replacementSeq[l++]=Gondol[id]; for (int j=last+1; j<a[i].F; j++) replacementSeq[l++]=j; last=a[i].F; } return l; } //---------------------- int countReplacement(int n, int inputSeq[]) { if (!valid(n,inputSeq)) return 0; int k=0; for (int i=0; i<n; i++) if (inputSeq[i]>n) k++; if (k<=1) return 1; int l=0,M=0,idx=-1; for (int i=0; i<n; i++) if (inputSeq[i]<=n) { idx=i; break; } for (int i=0; i<n; i++) a[i].F=inputSeq[i],a[i].S=i; sort(a,a+n); if (idx==-1) { for (int i=0; i<n; i++) Gondol[i]=i+1; } else { int x=inputSeq[idx]; Gondol[idx]=x; for (int i=idx+1; ; i++) { x++; if (x>n) x-=n; if (i==n) i-=n; if (i==idx) break; Gondol[i]=x; } } long long mod=1e9+9; long long ANS=1; int last=n; for (int i=0; i<n; i++) { if (a[i].F<=n) continue; int id=a[i].S; ANS=(1LL*ANS*(a[i].F-last))%mod; last=a[i].F; } return ANS; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | 7 ms | 504 KB | Output is correct |
7 | Correct | 13 ms | 760 KB | Output is correct |
8 | Correct | 11 ms | 632 KB | Output is correct |
9 | Correct | 5 ms | 504 KB | Output is correct |
10 | Correct | 12 ms | 760 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 | 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 | 7 ms | 504 KB | Output is correct |
7 | Correct | 14 ms | 748 KB | Output is correct |
8 | Correct | 11 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 504 KB | Output is correct |
10 | Correct | 13 ms | 760 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 7 ms | 632 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 14 ms | 760 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 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 | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 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 | 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 | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 3 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 | 14 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 436 KB | Output is correct |
11 | Correct | 31 ms | 1528 KB | Output is correct |
12 | Correct | 17 ms | 1784 KB | Output is correct |
13 | Correct | 18 ms | 1528 KB | Output is correct |
14 | Correct | 14 ms | 1528 KB | Output is correct |
15 | Correct | 24 ms | 2296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 528 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 504 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Incorrect | 2 ms | 376 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 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 | Incorrect | 2 ms | 376 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 504 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Incorrect | 2 ms | 376 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |