| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 118882 |
2019-06-20T00:30:59 Z |
ly20 |
Gondola (IOI14_gondola) |
C++17 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
using namespace std;
const int INF=1123456789,MAXN=250010,MOD=1e9+9,MAXL=32;
#define debug(args...) //fprintf(stderr,args)
map<int,int> vld;
int marc[MAXN];
#include "gondola.h"
int valid(int n,int seq[])
{
int mn=INF,at=INF,at2=INF,id0=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(st==0)
{
if(seq[i]>n)continue;
if(seq[i]<at && at==INF)
{
at=seq[i];mn=seq[i];
id0=(i+1-mn+n)%n;
}
else if(seq[i]<at)
{
at2=seq[i];st=1;
if(at2>mn)vl=0;
}
else
{
if((id0+seq[i]-1)%n!=i)vl=0;
at=seq[i];
}
}
else
{
if(seq[i]>n)continue;
if(seq[i]<at2 || seq[i]>mn || seq[i]>at)vl=0;
if((id0+seq[i]-1)%n!=i)vl=0;
at2=seq[i];
}
debug("%d %d %d\n",i,id0,(id0+seq[i])%n);
}
return vl;
}
int replacement(int n,int seq[],int replacementseq[])
{
vector<pair<int,int> > v;
int mn=INF,at=INF,at2=INF,id0=0,mx=0,imx=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
marc[seq[i]]=1;
if(mx<seq[i])imx=i;
mx=max(mx,seq[i]);
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(st==0)
{
if(seq[i]>n)continue;
if(seq[i]<at && at==INF)
{
at=seq[i];mn=seq[i];
id0=(i+1-mn+n)%n;
}
else if(seq[i]<at)
{
at2=seq[i];st=1;
if(at2>mn)vl=0;
}
else
{
if((id0+seq[i]-1)%n!=i)vl=0;
at=seq[i];
}
}
else
{
if(seq[i]>n)continue;
if(seq[i]<at2 || seq[i]>mn || seq[i]>at)vl=0;
if((id0+seq[i]-1)%n!=i)vl=0;
at2=seq[i];
}
debug("%d %d %d\n",i,id0,(id0+seq[i])%n);
}
int cnt=0,lst=(imx-id0+n)%n+1;
for(int i=0;i<n;i++)if(seq[i]>n && seq[i]!=mx)replacementseq[seq[i]-n-1]=(i-id0+n)%n+1;
for(int i=n+1;i<mx;i++)
{
if(!marc[i] && cnt==0)
{
replacementseq[i-n-1]=(imx-id0+n)%n+1;
cnt=1;
lst=i;
}
else if(!marc[i])
{
replacementseq[i-n-1]=lst;
lst=i;
}
}
for(int i=0;i<n;i++)if(seq[i]==mx)replacementseq[mx-n-1]=lst;
//for(int i=0;i<mx-n;i++)printf("%d ",replacementseq[i]);
//printf("\n");
return mx-n;
}
long long fst_exp(long long n,int k)
{
long long val=n;
long long resp=1;
for(int i=MAXL-1;i>=0;i--)
{
resp*=resp;
if(k&(1<<i))resp*=val;
if(resp>MOD)resp=resp%MOD;
}
return resp;
}
int countReplacement(int n,int seq[])
{
vector<int> v;
int mn=INF,at=INF,at2=INF,id0=0,mx=0,imx=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
if(seq[i]>n)v.push_back(seq[i]);
if(mx<seq[i])imx=i;
mx=max(mx,seq[i]);
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(st==0)
{
if(seq[i]>n)continue;
if(seq[i]<at && at==INF)
{
at=seq[i];mn=seq[i];
id0=(i+1-mn+n)%n;
}
else if(seq[i]<at)
{
at2=seq[i];st=1;
if(at2>mn)vl=0;
}
else
{
if((id0+seq[i]-1)%n!=i)vl=0;
at=seq[i];
}
}
else
{
if(seq[i]>n)continue;
if(seq[i]<at2 || seq[i]>mn || seq[i]>at)vl=0;
if((id0+seq[i]-1)%n!=i)vl=0;
at2=seq[i];
}
debug("%d %d %d\n",i,id0,(id0+seq[i])%n);
}
if(vl==0)return vl;
sort(v.begin(),v.end());
long long resp=1;
int cnt=0,lst=n;
for(int i=0;i<v.size();i++)
{
resp*=fst_exp(v.size()-i,v[i]-lst-1);
//printf("%lld %d %d %d %d\n",resp,v.size()-i,v[i]-lst-1,v[i],lst);
if(resp>MOD)resp%=MOD;
lst=v[i];
}
long long l=n*(n-1)/2/
l%=MOD;
if(v.size()==n)resp*=l;
if(v.size()==0)resp=1;
resp%=MOD;
//for(int i=0;i<mx-n;i++)printf("%d ",replacementseq[i]);
//printf("\n");
return resp;
}
/*int main()
{
int n;
int v[40],k[40];
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&v[i]);
printf("%d\n",countReplacement(n,v));
return 0;
}*/
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++)
~^~~~~~~~~
gondola.cpp:177:5: error: lvalue required as left operand of assignment
l%=MOD;
^~~
gondola.cpp:178:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size()==n)resp*=l;
~~~~~~~~^~~
gondola.cpp:168:6: warning: unused variable 'cnt' [-Wunused-variable]
int cnt=0,lst=n;
^~~
