Submission #17251

#TimeUsernameProblemLanguageResultExecution timeMemory
17251erdemkirazGondola (IOI14_gondola)C++98
100 / 100
106 ms7452 KiB
#include <bits/stdc++.h> using namespace std; #define type(x) __typeof((x).begin()) #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++) typedef long long ll; typedef pair < int, int > ii; const int inf = 1e9 + 333; const ll linf = 1e18 + inf; #include "gondola.h" int valid(int n, int inputSeq[]) { int ind = -1, x = -1; for(int i = 0; i < n; i++) { if(inputSeq[i] <= n) { ind = i; x = inputSeq[i]; break; } } for(int i = ind + 1; i < n; i++) { if(inputSeq[i] <= n and (x + i - ind - 1) % n + 1 != inputSeq[i]) return 0; } set < int > s; for(int i = 0; i < n; i++) s.insert(inputSeq[i]); return s.size() == n; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int ind = 1; for(int i = 0; i < n; i++) { if(gondolaSeq[i] <= n) { ind = (gondolaSeq[i] - 1 - i + n) % n + 1; break; } } vector < ii > v; for(int i = 0; i < n; i++) { v.push_back(ii(gondolaSeq[i], (ind + i - 1) % n + 1)); } sort(v.begin(), v.end()); int nxt = n + 1, sz = 0; foreach(it, v) { int x = it -> first; int i = it -> second; while(nxt <= x) { replacementSeq[sz++] = i; i = nxt; nxt++; } } return sz; } //---------------------- const int mod = 1e9 + 9; int power(int x, int k) { int res = 1; while(k) { if(k & 1) res = (ll) res * x % mod; x = (ll) x * x % mod; k >>= 1; } return res; } int countReplacement(int n, int inputSeq[]) { if(!valid(n, inputSeq)) return 0; int ans = 1; int mx = *max_element(inputSeq, inputSeq + n); set < int > s; for(int i = 0; i < n; i++) if(inputSeq[i] > n) s.insert(inputSeq[i]); int bef = n, cnt = 0; foreach(it, s) { int x = *it; ans = (ll) ans * power(s.size() - cnt, x - bef - 1) % mod; bef = x; cnt++; } if(*min_element(inputSeq, inputSeq + n) > n) ans = (ll) ans * n % mod; return 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...