Submission #1196373

#TimeUsernameProblemLanguageResultExecution timeMemory
1196373dostsGondola (IOI14_gondola)C++20
55 / 100
34 ms6728 KiB
#include "gondola.h" #include <bits/stdc++.h> #pragma GCC target("lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define sp << " " << using namespace std; int32_t valid(int32_t n, int32_t inputSeq[]) { map<int,int> saw; vi pos(n+1,-1); for (int i=0;i<n;i++) { if (saw.count(inputSeq[i])) return 0; saw[inputSeq[i]] = 1; if (inputSeq[i] <= n) { pos[inputSeq[i]] = i; } } int frst = -1; int lst = -1,lsty = -1; for (int j = 1;j<=n;j++) { if (pos[j] == -1) continue; if (frst == -1) frst = pos[j]; pos[j] = (pos[j]-frst+n)%n; if (lst != -1 && pos[j]-lst != j-lsty) return 0; lst = pos[j]; lsty = j; } return 1; } //---------------------- int32_t replacement(int32_t n, int32_t gondolaSeq[], int32_t replacementSeq[]) { int cur = n; vi inds(n+1); vi a(n+1); iota(all(a),0ll); int frst = -1; for (int i=1;i<=n;i++) { if (gondolaSeq[i-1] <= n) frst = i; } if (frst != -1) { a[frst] = gondolaSeq[frst-1]; for (int j = frst+1;j<=n;j++) a[j] = a[j-1]%n+1; for (int j = frst-1;j>=1;j--) a[j] = (a[j+1]==1)?n:(a[j+1]-1); } iota(all(inds),0ll); sort(1+all(inds),[&](int x,int y) { return gondolaSeq[x-1] < gondolaSeq[y-1]; }); int ptr = 0; for (int i = 1;i<=n;i++) { int ind = inds[i]; while (gondolaSeq[ind-1] > a[ind]) { replacementSeq[ptr++] = a[ind]; a[ind] = ++cur; } } return ptr; } //---------------------- const int MOD = 1e9+9; int mult(int x,int y) { return (x*y)%MOD; } int expo(int x,int y) { if (!y) return 1; int e = expo(x,y>>1); e = mult(e,e); if (y&1) e = mult(e,x); return e; } int32_t countReplacement(int32_t n, int32_t inputSeq[]) { int ans = valid(n,inputSeq); vi inds(n+1); iota(all(inds),0ll); sort(1+all(inds),[&](int x,int y) { return inputSeq[x-1] < inputSeq[y-1]; }); int rem = 0; for (int i=1;i<=n;i++) if (inputSeq[i-1] > n) rem++; int cur = n; for (int i=1;i<=n;i++) { int ind = inds[i]; if (inputSeq[ind-1] <= cur) assert(0); ans = mult(ans,expo(rem,(inputSeq[ind-1]-cur-1))); cur = inputSeq[ind-1]; rem--; } 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...