Submission #38838

#TimeUsernameProblemLanguageResultExecution timeMemory
38838adamczh1Gondola (IOI14_gondola)C++14
100 / 100
139 ms8928 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; int valid(int n, int inputSeq[]) { set<int> s; set<int> t; for(int i=0;i<n;i++){ if(inputSeq[i]<=n){ s.insert((i-inputSeq[i]+n)%n); } t.insert(inputSeq[i]); } return s.size()<=1 && t.size()==n; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { set<int> s; vector<int> loc(250001,-1); for(int i=0;i<n;i++){ if(gondolaSeq[i]<=n){ s.insert((i-gondolaSeq[i]+n)%n); } loc[gondolaSeq[i]]=i; } int l=0; int cur=n+1; if(s.size()==0){ for(int i=1;i<=250000;i++){ if(loc[i]==-1)continue; replacementSeq[l]=loc[i]+1; l++; cur++; while(cur<=i){ replacementSeq[l]=cur-1; l++; cur++; } } } else{ int dif=*s.begin(); for(int i=n+1;i<=250000;i++){ if(loc[i]==-1)continue; int tmp=(loc[i]-dif+n)%n; if(tmp==0)tmp=n; replacementSeq[l]=tmp; l++; cur++; while(cur<=i){ replacementSeq[l]=cur-1; l++; cur++; } } } return l; } //---------------------- int fpow(int a,int b,int mod){ if(b==0) return 1; if(b&1) return 1ll*fpow(a,b-1,mod)*a%mod; int tmp=fpow(a,b>>1,mod); return 1ll*tmp*tmp%mod; } int countReplacement(int n, int inputSeq[]) { int MOD=1e9+9; if(!valid(n,inputSeq)) return 0; set<int> s; for(int i=0;i<n;i++){ if(inputSeq[i]>n){ s.insert(inputSeq[i]); } } int x=s.size(); int cur=n; long long ans=1; for(int val:s){ ans*=fpow(x,val-cur-1,MOD); ans%=MOD; cur=val; x--; } if(s.size()==n){ ans*=n; ans%=MOD; } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:15:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return s.size()<=1 && t.size()==n;
                                ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s.size()==n){
             ^
#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...