Submission #1262945

#TimeUsernameProblemLanguageResultExecution timeMemory
1262945motionGondola (IOI14_gondola)C++20
50 / 100
12 ms2108 KiB
#include "gondola.h" #include<bits/stdc++.h> using namespace std; int valid(int n, int inputSeq[]) { int ind,val; for(int i=0;i<n;i++) { if(inputSeq[i]<=n) { ind=i; val=inputSeq[i]; } } val+=n; for(int i=ind-1;i>=0;i--) { if(inputSeq[i]<=n) { int k=(val-(ind-i))%n; if(k==0) k=n; if(inputSeq[i]!=k) { return 0; } } } for(int i=ind+1;i<n;i++) { if(inputSeq[i]<=n) { int k=(val-(ind-i))%n; if(k==0) k=n; if(inputSeq[i]!=k) { return 0; } } } sort(inputSeq,inputSeq+n); for(int i=1;i<n;i++) { if(inputSeq[i]==inputSeq[i-1]) { return 0; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int ind=0,val=1; vector<pair<int,int>> S; for(int i=0;i<n;i++) { if(gondolaSeq[i]<=n) { ind=i; val=gondolaSeq[i]; } } val+=n; for(int i=ind;i>=0;i--) { if(gondolaSeq[i]>n) { int k=(val-(ind-i))%n; if(k==0) k=n; S.push_back({gondolaSeq[i],k}); } } for(int i=ind+1;i<n;i++) { if(gondolaSeq[i]>n) { int k=(val+(i-ind))%n; if(k==0) k=n; S.push_back({gondolaSeq[i],k}); } } if(S.size()==0) return 0; sort(S.begin(),S.end()); int in=0,e=S[S.size()-1].first; int l=0; replacementSeq[l]=S[in].second; l++; for(int i=n+1;i<e;i++) { if(i==S[in].first) { in++; replacementSeq[l]=S[in].second; l++; } else { replacementSeq[l]=i; l++; } } return l; } //---------------------- int countReplacement(int n, int inputSeq[]) { int MOD=1e9+7; if(!valid(n,inputSeq)) return 0; long long ans=1; bool cz=1; int ind=0,val=1; vector<pair<int,int>> S; for(int i=0;i<n;i++) { if(inputSeq[i]<=n) { ind=i; val=inputSeq[i]; cz=0; } } val+=n; for(int i=ind;i>=0;i--) { if(inputSeq[i]>n) { int k=(val-(ind-i))%n; if(k==0) k=n; S.push_back({inputSeq[i],k}); } } for(int i=ind+1;i<n;i++) { if(inputSeq[i]>n) { int k=(val+(i-ind))%n; if(k==0) k=n; S.push_back({inputSeq[i],k}); } } if(S.size()==0) return 1; sort(S.begin(),S.end()); int in=0,e=S[S.size()-1].first; for(int i=n+1;i<e;i++) { if(i==S[in].first) { in++; } else { ans*=(S.size()-in); ans%=MOD; } } if(cz) { ans*=n; 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...