Submission #39717

#TimeUsernameProblemLanguageResultExecution timeMemory
39717funcsrGondola (IOI14_gondola)C++14
100 / 100
74 ms13336 KiB
#include "gondola.h" #include <iostream> #include <vector> #include <cassert> #include <set> #include <algorithm> #include <map> using namespace std; typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(x) x.begin(), x.end() #define MOD 1000000009 #define _1 first #define _2 second int A[100000], cur[100000]; map<int, int> cnt; bool glock; int valid(int N, int inputSeq[]) { cnt.clear(); rep(i, N) A[i] = inputSeq[i]-1; rep(i, N) cnt[A[i]]++; for (P p : cnt) if (p._2 > 1) return 0; int base = -1; rep(i, N) if (A[i] < N) base = (A[i]-i+N)%N; rep(i, N) cur[i] = (i+max(0,base))%N; glock = false; if (base == -1) return 1; glock = true; rep(i, N) if (A[i] < N && A[i] != cur[i]) return 0; return 1; } //---------------------- int rev[250000]; int replacement(int N, int gondolaSeq[], int replacementSeq[]) { set<int> unused; assert(valid(N, gondolaSeq)); rep(i, N) rev[A[i]] = i; rep(i, N) if (A[i] >= N) unused.insert(i); int m = *max_element(A, A+N); int c = 0; for (int i=N; i<=m; i++) { int p = -1; if (cnt[i]) { p = rev[i]; unused.erase(rev[i]); } else p = *unused.begin(); replacementSeq[c++] = cur[p]+1; cur[p] = i; } return c; } //---------------------- int modpow(int x, int k) { int a = 1; while (k) { if (k&1) a = (1LL*a*x)%MOD; x = (1LL*x*x)%MOD; k>>=1; } return a; } int countReplacement(int N, int inputSeq[]) { if (valid(N, inputSeq) == 0) return 0; int unused = 0; rep(i, N) if (A[i] >= N) unused++; int m = *max_element(A, A+N); int s = 1; if (!glock) s *= N; int c = 0; int lp = N-1; for (P p : cnt) { if (p._1 < N) continue; s = (1LL*s*modpow(unused, p._1-lp-1)) % MOD; unused--; lp = p._1; } return s; }

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:72:7: warning: unused variable 'm' [-Wunused-variable]
   int m = *max_element(A, A+N);
       ^
gondola.cpp:75:7: warning: unused variable 'c' [-Wunused-variable]
   int c = 0;
       ^
#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...