Submission #586971

#TimeUsernameProblemLanguageResultExecution timeMemory
586971krit3379Gondola (IOI14_gondola)C++17
75 / 100
44 ms4520 KiB
#include<bits/stdc++.h> using namespace std; #include "gondola.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define N 100005 int valid(int n, int a[]){ int i; long long mod=1e18; set<int> s; for(i=0;i<n;i++){ if(s.count(a[i]))return 0; s.insert(a[i]); if(a[i]>n)continue; if(mod==1e18)mod=(i-a[i]+n)%n; else if(mod!=(i-a[i]+n)%n)return 0; } return 1; } int replacement(int n, int a[], int b[]){ int i,j,now,last,cnt; vector<pair<int,int>> v; for(i=0;i<n;i++)if(a[i]>n)v.push_back({a[i],i}); for(i=0;i<n;i++){ if(a[i]<=n){ now=a[i]; for(j=i+1;j<n;j++){ now++; if(now==n+1)now=1; a[j]=now; } for(j=0;j<i;j++){ now++; if(now==n+1)now=1; a[j]=now; } break; } } if(i==n)for(i=0;i<n;i++)a[i]=i+1; sort(v.begin(),v.end()); i=0; last=n; for(auto [now,x]:v){ cnt=now-last; while(cnt--)b[i++]=a[x],a[x]=i+n; last=now; } return i; } long long mod=1e9+9; long long bp(long long a,long long b){ if(b==0)return 1; long long temp=bp(a,b/2); if(b%2)return temp*temp%mod*a%mod; return temp*temp%mod; } int countReplacement(int n, int a[]){ int i,len,last; long long ans=1; vector<int> v; if(!valid(n,a))return 0; for(i=0;i<n;i++)if(a[i]>n)v.push_back(a[i]); sort(v.begin(),v.end()); len=v.size(); last=n; for(i=0;i<len;i++){ ans=ans*bp(len-i,v[i]-last-1)%mod; last=v[i]; } if(len==n)for(i=2;i<=n;i++)ans=ans*i%mod; 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...