Submission #1204813

#TimeUsernameProblemLanguageResultExecution timeMemory
1204813ereringGondola (IOI14_gondola)C++20
60 / 100
12 ms2368 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; #define pb push_back int valid(int n, int inputSeq[]) { bool flag=1; int req=-1; for(int i=0;i<n;i++){ if(req==-1 && inputSeq[i]<=n)req=inputSeq[i]+1; else if(inputSeq[i]<=n && req!=inputSeq[i])flag=0; else if(req!=-1)req++; if(req>n)req=1; } sort(inputSeq,inputSeq+n); for(int i=1;i<n;i++){ if(inputSeq[i]==inputSeq[i-1])return 0; } return flag; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int og[n],crnt=n+1,idx=0; vector<pair<int,int>> vec; for(int i=0;i<n;i++){ og[i]=i+1; if(gondolaSeq[i]<=n){ og[i]=gondolaSeq[i]; for(int j=i+1;j<n;j++){ og[j]=og[j-1]+1; if(og[j]>n)og[j]=1; } if(i>0)og[0]=og[n-1]+1; if(og[0]>n)og[0]=1; for(int j=1;j<i;j++){ og[j]=og[j-1]+1; if(og[j]>n)og[j]=1; } break; } } for(int i=0;i<n;i++)vec.pb({gondolaSeq[i],og[i]}); sort(vec.begin(),vec.end()); for(int i=0;i<n;i++){ while(vec[i].first>=crnt){ replacementSeq[idx++]=vec[i].second; vec[i].second=crnt; crnt++; } } return idx; } //---------------------- long long MOD=1e9+7; long long fast_pow(long long base,long long p,long long rem=1){ if(p==0)return 1; base%=MOD; rem%=MOD; if(p==1)return base*rem%MOD; if(p%2)return fast_pow(base*base,p/2,rem*base); return fast_pow(base*base,p/2,rem); } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq))return 0; sort(inputSeq,inputSeq+n); long long ans=1,crnt=n+1; bool flag=1; for(int i=0;i<n;i++){ if(inputSeq[i]<=n)flag=0; if(inputSeq[i]>=crnt){ ans*=fast_pow(n-i,inputSeq[i]-crnt); crnt=inputSeq[i]+1; } ans%=MOD; } if(flag)ans*=n; 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...