Submission #232103

#TimeUsernameProblemLanguageResultExecution timeMemory
232103spdskatrGondola (IOI14_gondola)C++14
90 / 100
32 ms2808 KiB
#include "gondola.h" #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <utility> #define fi first #define se second #define MOD 1000000009 using namespace std; typedef pair<int, int> pii; int valid(int n, int inputSeq[]) { int offset = -1; for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) { offset = (i - inputSeq[i] + 1 + n) % n; break; } } if (offset == -1) return 1; else { for (int i = 0; i < n; i++) { int ind = (offset+i) % n; if (inputSeq[ind] < n && inputSeq[ind] != i+1) return 0; } } return 1; } //---------------------- namespace T2 { int original[100005], cnt; vector<pii> elems; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int offset = -1; for (int i = 0; i < n; i++) { if (gondolaSeq[i] <= n) { offset = (i - gondolaSeq[i] + 1 + n) % n; break; } } if (offset == -1) { for (int i = 0; i < n; i++) original[i] = i+1; } else { for (int i = 0; i < n; i++) { original[(offset+i)%n] = i+1; } } for (int i = 0; i < n; i++) { if (gondolaSeq[i] > n) { elems.push_back({ gondolaSeq[i], i }); } } sort(elems.begin(), elems.end()); int cur = n+1; for (int i = 0; i < elems.size(); i++) { while (elems[i].fi >= cur) { replacementSeq[cnt++] = original[elems[i].se]; original[elems[i].se] = cur++; } } return cnt; } } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { return T2::replacement(n, gondolaSeq, replacementSeq); } //---------------------- namespace T3 { typedef long long ll; vector<pii> elems; ll ex(ll n, ll p) { ll res = 1, cur = n; for (int b = 0; p > 0; b++) { if ((p >> b) & 1) { res = (res * cur) % MOD; p ^= (1 << b); } cur = (cur * cur) % MOD; } return res; } int countReplacement(int n, int inputSeq[]) { int offset = -1; ll ans = 1; for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) { offset = (i - inputSeq[i] + 1 + n) % n; break; } } if (offset == -1) { ans *= n; } else { for (int i = 0; i < n; i++) { int ind = (offset+i) % n; if (inputSeq[ind] < n && inputSeq[ind] != i+1) return 0; } } for (int i = 0; i < n; i++) { if (inputSeq[i] > n) { elems.push_back({ inputSeq[i], i }); } } sort(elems.begin(), elems.end()); int cur = n+1; for (int i = 0; i < elems.size(); i++) { if (elems[i].fi < cur) return 0; ll p = (elems[i].fi - cur); ans = (ans * (ex(elems.size() - i, p) % MOD)) % MOD; cur = elems[i].fi + 1; } return (int)ans; } } int countReplacement(int n, int inputSeq[]) { return T3::countReplacement(n, inputSeq); }

Compilation message (stderr)

gondola.cpp: In function 'int T2::replacement(int, int*, int*)':
gondola.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < elems.size(); i++) {
                   ~~^~~~~~~~~~~~~~
gondola.cpp: In function 'int T3::countReplacement(int, int*)':
gondola.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < elems.size(); i++) {
                   ~~^~~~~~~~~~~~~~
#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...