| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 638390 | ggoh | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<gondola.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
lint X=1e9+9;
lint po(lint p,int q)
{
if(q==0)return 1ll;
if(q==1)return p;
lint o=po(p,q/2);
o=o*o%X;
if(q%2)return o*p%X;
else return o;
}
int valid(int n, int inputSeq[])
{
vector<int>check(n+1),copy(n);
for(int i=0;i<n;i++)
{
copy[i]=inputSeq[i];
if(inputSeq[i]<=n)check[inputSeq[i]]=i+1;
}
sort(copy.begin(),copy.end());
for(int i=0;i<n;i++)if(copy[i]==copy[i+1])return 0;
int c=0,ans=1,pos,t;
for(int i=1;i<=n;i++)
{
if(check[i])
{
if(!c)c=i,pos=check[i];
else
{
t=check[i]-pos;
if(t<=0)t+=n;
if(t!=i-c)ans=0;
}
}
}
return ans;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int>top(n),ans;
int c=0,pos;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<=n)
{
c=gondolaSeq[i];
pos=i;
}
}
int left=0;
if(c)
{
left=pos-(c-1);
}
vector<pair<int,int>>newG;
for(int i=0;i<n;i++)
{
top[i]=i+1;
newG.push_back({gondolaSeq[i],(i+n-left)%n});
}
sort(newG.begin(),newG.end());
int t=n+1;
for(auto &k:newG)
{
if(top[k.second]==k.first)continue;
ans.push_back(top[k.second]);
top[k.second]=t;
t++;
while(top[k.second]!=k.first)
{
ans.push_back(top[k.second]);
top[k.second]++;
t++;
}
}
int sz=(int)ans.size();
for(int i=0;i<sz;i++)replacementSeq[i]=ans[i];
return sz;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))return 0;
lint ans=1ll,mul;
vector<int>top(n),ans;
int c=0,pos;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n)
{
c=inputSeq[i];
pos=i;
}
}
int left=0;
if(c)
{
left=pos-(c-1);
}
vector<pair<int,int>>newG;
for(int i=0;i<n;i++)
{
top[i]=i+1;
newG.push_back({inputSeq[i],(i+n-left)%n});
}
mul=n;
sort(newG.begin(),newG.end());
int t=n+1;
for(auto &k:newG)
{
if(k.first==k.second+1)mul--;
else
{
ans*=po(mul,k.first-t);
ans%=X;
t=k.first+1;
mul--;
}
}
return ans;
}