제출 #168546

#제출 시각아이디문제언어결과실행 시간메모리
168546johutha곤돌라 (IOI14_gondola)C++14
75 / 100
28 ms2348 KiB
#include "gondola.h" #include <vector> #include <algorithm> #include <iostream> #define int int64_t using namespace std; const int mod = 1000000009; signed fastpowmod(int base, int exp) { int res = 1; for (; exp; exp /= 2) { if (exp & 1) res = (res*base) % mod; base *= base; } return res; } signed valid(signed n, signed inputSeq[]) { vector<int> dcheck; for (int i = 0; i < n; i++) { inputSeq[i]--; dcheck.push_back(inputSeq[i]); } sort(dcheck.begin(), dcheck.end()); for (int i = 1; i < n; i++) { if (dcheck[i] == dcheck[i - 1]) return 0; } int zval = 0; for (int i = 0; i < n; i++) { if (inputSeq[i] < n) { zval = inputSeq[i] - i; break; } } for (int i = 0; i < n; i++) { if (inputSeq[i] < n) { if ((zval + i + n) % n != inputSeq[i]) return 0; } } return 1; } //---------------------- signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]) { vector<int> Seq; for (int i = 0; i < n; i++) Seq.push_back(gondolaSeq[i] - 1); int zval = 0; for (int i = 0; i < n; i++) { if (Seq[i] < n) { zval = Seq[i] - i; break; } } rotate(Seq.rbegin(), Seq.rbegin() + ((zval + n) % n), Seq.rend()); int mmax = *max_element(Seq.begin(), Seq.end()); int mind = -1; for (int i = 0; i <= mmax - n; i++) replacementSeq[i] = -1; for (int i = 0; i < n; i++) { if (Seq[i] == mmax) mind = i; if (Seq[i] >= n) replacementSeq[Seq[i] - n] = i + 1; } mind++; for (int i = 0; i <= mmax - n; i++) { if (replacementSeq[i] == -1) { replacementSeq[i] = mind; mind = n + i + 1; } } replacementSeq[mmax - n] = mind; return mmax - n + 1; } //---------------------- signed countReplacement(signed n, signed inputSeq[]) { if (!valid(n, inputSeq)) return 0; vector<int> Seq; for (int i = 0; i < n; i++) Seq.push_back(inputSeq[i]); sort(Seq.begin(), Seq.end()); int last = n - 1; int res = 1; bool defined = false; for (int i = 0; i < n; i++) { if (Seq[i] < n) { defined = true; continue; } int len = Seq[i] - last - 1; last = Seq[i]; res = (res * fastpowmod(n - i, len)) % mod; } if (!defined) { for (int i = 1; i <= n; i++) { res = (res * i) % mod; } } return res; }
#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...