Submission #57591

#TimeUsernameProblemLanguageResultExecution timeMemory
57591vexGondola (IOI14_gondola)C++14
50 / 100
40 ms8772 KiB
#include<bits/stdc++.h> #include<gondola.h> #define maxn 250005 #define MOD 1000000009 #define pii pair<int,int> using namespace std; int b[maxn]; int valid(int n, int a[]) { int minn=0; for(int i=1;i<n;i++)if(a[i]<a[minn])minn=i; for(int i=0;i<n;i++)b[i]=a[(i+minn)%n]; if(b[0]>n)return 1; sort(a,a+n); for(int i=0;i<n-1;i++)if(a[i]==a[i+1])return 0; int pre=0; for(int i=1;i<n;i++) { if(b[i]<=n) { if(b[i]-b[pre]!=i-pre)return 0; pre=i; } } return 1; } vector<pii>v; int replacement(int n, int g[], int r[]) { if(!valid(n,g))return -1; int s=b[0]; for(int i=0;i<n;i++)if(b[i]>n) { int br=(s+i)%n;if(br==0)br=n; v.push_back({b[i],br}); } sort(v.begin(),v.end()); int len=v.size(); if(len==0) { return 0; } int duz=0; for(int i=0;i<len;i++) { r[duz]=v[i].second;duz++; int pre=n; if(i!=0)pre=v[i-1].first; for(int j=pre+1;j<v[i].first;j++) { r[duz]=j; duz++; } } return v[len-1].first-n; } long long ste(int x,int y) { if(y==0)return 1; if(y%2==1)return (ste(x,y-1)*x)%MOD; long long res=ste(x,y/2); return (res*res)%MOD; } vector<int>br; int countReplacement(int n, int a[]) { if(!valid(n,a))return 0; for(int i=0;i<n;i++)if(b[i]>n)br.push_back(b[i]); sort(br.begin(),br.end()); long long sol=1; int len=br.size(); for(int i=0;i<len;i++) { int pre=n; if(i!=0)pre=br[i-1]; sol*=ste(len-i,br[i]-pre-1); } return sol; }
#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...