제출 #428428

#제출 시각아이디문제언어결과실행 시간메모리
428428TLP39곤돌라 (IOI14_gondola)C++14
75 / 100
48 ms4512 KiB
#include "gondola.h" #include<bits/stdc++.h> using namespace std; typedef long long int ll; int valid(int n, int seq[]) { map<int,int> mp; bool ch=true; int temp=-1; for(int i=0;i<n;i++) { if(seq[i]<=n) { if(ch) { ch=false; temp=(seq[i]-i+n)%n; } else if((seq[i]-i+n)%n!=temp) return 0; } if(mp[seq[i]]) return 0; else mp[seq[i]]=1; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int ma=-1; for(int i=0;i<n;i++) ma=max(gondolaSeq[i],ma); int permu=1; for(int i=0;i<n;i++) { if(gondolaSeq[i]<=n) { permu=(gondolaSeq[i]-i+n)%n; } } int gondo[250010]={}; for(int i=0;i<n;i++) gondo[gondolaSeq[i]]=(i+n-1+permu)%n+1; int onpath[250010]={}; for(int i=1;i<=n;i++) onpath[i]=i; int temp=gondo[ma]; for(int i=n+1;i<=ma;i++) { if(gondo[i]) { replacementSeq[i-n-1]=onpath[gondo[i]]; onpath[gondo[i]]=i; } else { replacementSeq[i-n-1]=onpath[temp]; onpath[temp]=i; } } return ma-n; } //---------------------- ll big=1000000009; ll expo(int x,int y) { if(y==0) return 1ll; if(y==1) return (long long)x; if(y&1) return ((((expo(x,y>>1))*(expo(x,y>>1)))%big)*(long long)x)%big; return ((expo(x,y>>1))*(expo(x,y>>1)))%big; } ll facto(int m) { if(m<=1) return 1ll; return ((long long)m*facto(m-1))%big; } int countReplacement(int n, int inputSeq[]) { ll res=1; if(!valid(n,inputSeq)) return 0; bool ch=false; int ti[n]; for(int i=0;i<n;i++) { ti[i]=inputSeq[i]; if(ti[i]<=n) ch=true; } sort(ti,ti+n); for(int i=n-1;i>=0;i--) { if(ti[i]<=n) break; if(i) res*=expo(n-i,ti[i]-max(ti[i-1],n)-1); else res*=expo(n,ti[0]-n-1); res%=big; } if(!ch) { res*=facto(n); res%=big; } return (int)res; }
#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...