Submission #590592

#TimeUsernameProblemLanguageResultExecution timeMemory
590592promaGondola (IOI14_gondola)C++17
60 / 100
21 ms2192 KiB
#include "gondola.h" #include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 1e9+7; int bp(int a, int n) { if (!n) return 1; if (n % 2) return a * bp(a, n - 1) % MOD; int b = bp(a, n / 2); return b * b % MOD; } int32_t valid(int32_t n, int32_t inputSeq[]) { vector <int> a(n); int flag = 0; for (int i = 0; i < n; i ++) { if (inputSeq[i] <= n) { a[i] = inputSeq[i]; for (int j = i + 1; j < n; j ++) { a[j] = (a[j-1] + 1) % n; if (!a[j]) a[j] = n; } if (i) { a[0] = (a[n-1] + 1) % n; if (!a[0]) a[0] = n; } for (int j = 1; j < i; j ++) { a[j] = (a[j-1] + 1) % n; if (!a[j]) a[j] = n; } flag = 1; break; } } vector <int> tmp(n); for (int i = 0; i < n; i ++) { tmp[i] = inputSeq[i]; } sort(tmp.begin(), tmp.end()); for (int i = 1; i < n; i ++) { if (tmp[i] == tmp[i-1]) return 0; } if (!flag) return 1; for (int i = 0; i < n; i ++) { if (inputSeq[i] <= n and inputSeq[i] != a[i]) return 0; } return 1; } //---------------------- int32_t replacement(int32_t n, int32_t gondolaSeq[], int32_t replacementSeq[]) { vector <int> a(n); vector <pair <int, int>> p; int flag = 0; for (int i = 0; i < n; i ++) { if (gondolaSeq[i] <= n) { a[i] = gondolaSeq[i]; for (int j = i + 1; j < n; j ++) { a[j] = (a[j-1] + 1) % (n + 1); a[j] = max(1ll, a[j]); } if (i) { a[0] = (a[n-1] + 1) % (n + 1); a[0] = max(1ll, a[0]); } for (int j = 1; j < i; j ++) { a[j] = (a[j-1] + 1) % (n + 1); a[j] = max(1ll, a[j]); } flag = 1; break; } } if (!flag) { for (int i = 0; i < n; i ++) { a[i] = i + 1; } } for (int i = 0; i < n; i ++) { if (gondolaSeq[i] > n) p.push_back({gondolaSeq[i], a[i]}); } sort(p.begin(), p.end()); int last = n + 1, pos = 0; for (auto i: p) { replacementSeq[pos ++] = i.second; while (last < i.first) { replacementSeq[pos ++] = last ++; } last = i.first + 1; } return pos; } //---------------------- int32_t countReplacement(int32_t n, int32_t inputSeq[]) { if (!valid(n, inputSeq)) return 0; vector <int> v = {n}; int flag = 1; for (int i = 0; i < n; i ++) { if (inputSeq[i] > n) v.push_back(inputSeq[i]); else flag = 0; } sort(v.begin(), v.end()); int m = v.size(); int ans = 1; if (flag) ans = n; for (int i = 1; i < m; i ++) { ans *= bp(m - i, v[i] - v[i-1] - 1); ans %= 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...