제출 #589069

#제출 시각아이디문제언어결과실행 시간메모리
589069Mamedov곤돌라 (IOI14_gondola)C++17
60 / 100
49 ms4672 KiB
#pragma GCC optimize ("O3") #include "gondola.h" #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int valid(int n, int inputSeq[]) { set<int>s(inputSeq, inputSeq + n); if (size(s) < n) return 0; int shift = -1; for (int i = 0; i < n; ++i) { if (inputSeq[i] <= n) { if (shift == -1) shift = (inputSeq[i] - (i + 1) + n) % n; else if ((inputSeq[i] - (i + 1) + n) % n != shift) { return 0; } } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int shift = 0; vector<pii>rep; for (int i = 0; i < n; ++i) { if (gondolaSeq[i] <= n) { shift = (gondolaSeq[i] - (i + 1) + n) % n; break; } } for (int i = 0; i < n; ++i) { if (gondolaSeq[i] > n) { rep.eb(mpr(gondolaSeq[i], (i + shift) % n + 1)); } } rep.eb(mpr(n, n)); int ptr = 0; sort(all(rep), greater<pii>()); int sz = size(rep); for (int i = 0; i < sz - 1; ++i) { for (int j = rep[i].f - 1; j > rep[i + 1].f; --j) { replacementSeq[ptr++] = j; } replacementSeq[ptr++] = rep[i].s; } reverse(replacementSeq, replacementSeq + ptr); return ptr; } //---------------------- const int mod = 1e9 + 9; int binPow(int a, int n) { if (n == 0) return 1; if ((n & 1)) return (1ll * a * binPow(a, n - 1)); else return binPow((1ll * a * a) % mod, n / 2); } int countReplacement(int n, int inputSeq[]) { if (!valid(n, inputSeq)) return 0; vector<int>rep; for (int i = 0; i < n; ++i) { if (inputSeq[i] > n) { rep.eb(inputSeq[i]); } } rep.eb(n); sort(all(rep), greater<int>()); int sz = size(rep); int res = 1; for (int i = 1; i < sz; ++i) { res = (1ll * res * binPow(i, rep[i - 1] - rep[i] - 1)) % mod; } if (sz == n + 1) { res = (1ll * n * res) % 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...