제출 #155048

#제출 시각아이디문제언어결과실행 시간메모리
155048junodeveloper곤돌라 (IOI14_gondola)C++14
60 / 100
19 ms2040 KiB
#include "gondola.h" #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() #define sz(x) (int)x.size() #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+9; int valid(int n, int inputSeq[]) { int i; vector<bool> chk(250005,false); for(i=0;i<n;i++) { if(chk[inputSeq[i]]) return 0; chk[inputSeq[i]]=true; } int p=-1,t; for(i=0;i<n;i++) { if(inputSeq[i]<=n) { t=(i-inputSeq[i]+1+n)%n; if(p!=-1&&t!=p) return 0; p=t; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int i,j,p=0; for(i=0;i<n;i++) { if(gondolaSeq[i]<=n) { p=(i-gondolaSeq[i]+1+n)%n; break; } } vector<pii> v; for(i=0;i<n;i++) { if(gondolaSeq[i]>n) { v.push_back(make_pair(gondolaSeq[i],i)); } } sort(all(v)); int cur=n+1,top=0; for(i=0;i<sz(v);i++) { if(v[i].se>=p) j=v[i].se-p+1; else j=n-p+v[i].se+1; replacementSeq[top++]=j; while(cur<v[i].fi) replacementSeq[top++]=cur++; } return top; } //---------------------- int modpow(int a,int n) { int r=1,b=a; while(n>0) { if(n&1) r=(ll)r*b%mod; b=(ll)b*b%mod; n>>=1; } return r; } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq)) return 0; vector<int> v; int i; for(i=0;i<n;i++) { if(inputSeq[i]>n) v.push_back(inputSeq[i]); } if(v.empty()) return 1; v.push_back(n); sort(all(v)); int res=1; for(i=0;i+1<sz(v);i++) { res=(ll)res*modpow(sz(v)-i-1,v[i+1]-v[i]-1)%mod; } if(sz(v)==n+1) { res=(ll)res*n%mod; } return 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...