제출 #12708

#제출 시각아이디문제언어결과실행 시간메모리
12708qja0950곤돌라 (IOI14_gondola)C++98
100 / 100
80 ms9888 KiB
#include "gondola.h" #include <algorithm> #include <set> using namespace std; #define MAX_N 101101 #define MAX_V 250052 #define MOD 1000000009 typedef long long ll; int CheckV[MAX_V]; int valid(int n, int inputSeq[]) { for(int i=0; i<n; i++) { int now = inputSeq[i]; CheckV[now]++; if(CheckV[now] > 1) return 0; } int first = -1; for(int i=0; i<n; i++) { int now = inputSeq[i]; if(now > n) continue; first = i; break; } if(first == -1) return 1; for(int i=0; i<n; i++) { int index = (first + i) % n; int value = (inputSeq[first] + i - 1) % n + 1; int now = inputSeq[index]; if(now > n) continue; if(now != value) return 0; } return 1; } //---------------------- struct SORTR{ int index; int value; }SortR[MAX_N]; bool operator<(SORTR X, SORTR Y) { return X.value < Y.value; } int State[MAX_N]; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int first = 0; for(int i=0; i<n; i++) { int now = gondolaSeq[i]; if(now > n) continue; first = i; break; } for(int i=0; i<n; i++) { int index = (first + i) % n; int value = (gondolaSeq[first] + i - 1) % n + 1; State[index] = value; SortR[i].index = i; SortR[i].value = gondolaSeq[i]; } sort(SortR, SortR+n); int cnt = 0; int now = n; for(int i=0; i<n; i++) { int nowindex = SortR[i].index; int nowvalue = SortR[i].value; if(nowvalue < n) continue; while(State[nowindex] != nowvalue) { replacementSeq[cnt++] = State[nowindex]; State[nowindex] = ++now; } } return cnt; } //---------------------- set<int> CheckSame; ll Ans = 1; struct SORTC{ int index; int value; }SortC[MAX_N]; bool operator<(SORTC X, SORTC Y) { return X.value < Y.value; } ll GetPower(int x, int k) { ll result = 1; ll powerx = x; while(k) { if(k%2 == 1) { result *= powerx; result %= MOD; } powerx *= powerx; powerx %= MOD; k/=2; } return result; } int countReplacement(int n, int inputSeq[]) { for(int i=0; i<n; i++) { int now = inputSeq[i]; if(CheckSame.find(now) != CheckSame.end()) return 0; CheckSame.insert(now); } int first = -1; for(int i=0; i<n; i++) { int now = inputSeq[i]; if(now > n) continue; first = i; break; } if(first == -1) { Ans = n; first = 0; } for(int i=0; i<n; i++) { SortC[i].index = i; SortC[i].value = inputSeq[i]; } sort(SortC, SortC+n); int last = n; for(int i=0; i<n; i++) { int nowvalue = SortC[i].value; if(nowvalue < n) continue; int count = n - i; Ans *= GetPower(count, nowvalue - last - 1); Ans %= MOD; last = nowvalue; } return (int)Ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...