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<algorithm>
#include<map>
#include<string.h>
using namespace std;
map<int,int>visit2;
int a[100010],ch[250010],visit[250010];
struct data
{
int x,y;
bool operator<(const data&r)const
{
return x<r.x;
}
}arr[250010];
int valid(int n, int inputSeq[])
{
int i,k=0;
for(i=0;i<n;i++)
{
if(visit[inputSeq[i]]==1) return 0;
visit[inputSeq[i]]=1;
if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
}
for(i=1;i<=n;i++)
{
if(ch[i]!=0 && k==0)
{
k=ch[i];
continue;
}
if(k!=0)
{
k++;
if(k>n) k=1;
}
if(ch[i]!=0 && k!=ch[i]) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int s,i,big=0,k=1,w=0,top=0,pos=0,p=0;
for(i=0;i<n;i++)
{
ch[gondolaSeq[i]]=1;
if(gondolaSeq[i]<=n) visit[i]=1;
if(big<gondolaSeq[i]) big=gondolaSeq[i];
if(gondolaSeq[i]<=n) pos=i,p=gondolaSeq[i];
}
for(i=0;i<n;i++)
{
if(visit[i]==0)
{
top++;
arr[top].x=gondolaSeq[i];
arr[top].y=i;
}
}
sort(arr+1,arr+top+1);
if(p==0)
{
for(i=0;i<n;i++) a[i]=i+1;
}
else
{
for(i=pos;i<=pos+n-1;i++)
{
a[i%n]=p;
p++;
if(p==n+1) p=1;
}
}
for(i=n+1;i<=big;i++)
{
if(ch[i]==0)
{
replacementSeq[w++]=a[arr[k].y];
a[arr[k].y]=i;
}
else
{
replacementSeq[w++]=a[arr[k].y];
a[arr[k].y]=i;
k++;
}
}
return w;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int s,i,big=0,k=0,w=0,top=0,pos=0,p=0;
long long int dap=1,c;
for(i=0;i<n;i++)
{
if(visit2[inputSeq[i]]==1) return 0;
visit2[inputSeq[i]]=1;
if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
}
for(i=1;i<=n;i++)
{
if(ch[i]!=0 && k==0)
{
k=ch[i];
continue;
}
if(k!=0)
{
k++;
if(k>n) k=1;
}
if(ch[i]!=0 && k!=ch[i]) return 0;
}
k=1;
memset(ch,0,sizeof ch);
for(i=0;i<n;i++)
{
ch[inputSeq[i]]=1;
if(inputSeq[i]<=n) visit[i]=1;
if(big<inputSeq[i]) big=inputSeq[i];
if(inputSeq[i]<=n) pos=i,p=inputSeq[i];
}
for(i=0;i<n;i++)
{
if(visit[i]==0)
{
top++;
arr[top].x=inputSeq[i];
arr[top].y=i;
}
}
sort(arr+1,arr+top+1);
if(p==0)
{
for(i=0;i<n;i++) a[i]=i+1;
dap=n;
}
else
{
for(i=pos;i<=pos+n-1;i++)
{
a[i%n]=p;
p++;
if(p==n+1) p=1;
}
}
c=top;
for(i=n+1;i<=big;i++)
{
if(ch[i]==1)
{
c--;
continue;
}
if(c>0) dap*=c;
dap%=1000000009;
}
return dap;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |