제출 #586769

#제출 시각아이디문제언어결과실행 시간메모리
586769Red_Inside곤돌라 (IOI14_gondola)C++17
55 / 100
21 ms3028 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define forn(j, i, n) for(int i = j; i <= n; ++i) #define FOR(j, i, n) for(int i = j; i < n; ++i) #define nfor(j, i, n) for(int i = n; i >= j; --i) #define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie(); #define all(v) v.begin(), v.end() #define pb push_back const int maxn = 3e5+100; //#define int ll #define pii pair <int, int> int inf = 1e9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a[maxn], was[maxn], b[maxn]; int valid(int n, int inputSeq[]) { forn(1, i, n) { a[i] = inputSeq[i-1]; was[a[i]]++; if(was[a[i]] >= 2) { return 0; } } int start = -1; forn(1, i, n) { if(a[i] <= n) { start = i - a[i] + 1; break; } } if(start == -1) return 1; forn(1, i, n) { b[(i-start+n)%n+1] = a[i]; } forn(1, i, n) { if(b[i] > n) continue; if(b[i] != i) return 0; } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { forn(1, i, n) { a[i] = gondolaSeq[i-1]; } int start = -1; forn(1, i, n) { if(a[i] <= n) { start = i - a[i] + 1; break; } } if(start == -1) { set <pii> st; forn(1, i, n) { if(a[i] > n) { st.insert({a[i], i}); } } int cur = 0; while(st.size()) { replacementSeq[cur] = st.begin()->s; cur++; while(n + cur < st.begin()->f) { replacementSeq[cur] = n + cur; cur++; } st.erase(st.begin()); } return cur; } forn(1, i, n) { b[(i-start+n)%n+1] = a[i]; } set <pii> st; forn(1, i, n) { if(b[i] > n) { st.insert({b[i], i}); } } int cur = 0; while(st.size()) { replacementSeq[cur] = st.begin()->s; cur++; while(n + cur < st.begin()->f) { replacementSeq[cur] = n + cur; cur++; } st.erase(st.begin()); } return cur; } //---------------------- ll mod = 1e9+9; ll binpow(ll a, ll n) { ll res = 1; while(n) { if(n&1) { res = res * a % mod; } a = a * a % mod; n /= 2; } return res; } int countReplacement(int n, int inputSeq[]) { if(!valid(n, inputSeq)) { return 0; } forn(1, i, n) { a[i] = inputSeq[i-1]; } int start = 0; forn(1, i, n) { if(a[i] <= n) { start = 1; break; } } set <pii> st; forn(1, i, n) { if(a[i] > n) { st.insert({b[i], i}); } } ll ans = 1; int last = n; while(st.size()) { ans *= binpow((ll)(st.size()), st.begin()->f - last - 1); ans %= mod; last = st.begin()->f; st.erase(st.begin()); } if(!start) ans = ans * n % 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...