Submission #127884

#	Time	Username	Problem	Language	Result	Execution time	Memory
127884		zozder	Gondola (IOI14_gondola)	C++14	60 / 100	23 ms	2936 KiB

gondola

#include "gondola.h"
#include <iostream>
using namespace std;
 
int valid(int n, int inputSeq[])
{
	int minn=10000,minl=n;
	int tag[250001];
	for(int i=1;i<=250000;i++)tag[i]=0;
	for(int i=0;i<n;i++)if(inputSeq[i]<minn&&0<inputSeq[i]&&inputSeq[i]<=n)
	{
		minn=inputSeq[i];
		minl=i;
  	}
	int t=1,m=n;
	while(m>0)
  	{
  		if(minl>=n)minl=0;
  		
  		if((inputSeq[minl]!=minn&&0<inputSeq[minl]&&inputSeq[minl]<=n)||tag[inputSeq[minl]]==1)t=0;
  		tag[inputSeq[minl]]=1;
//  		cout<<minn<<","<<minl<<","<<inputSeq[minl]<<","<<tag[inputSeq[minl]]<<endl;
  		m--;
		minl++;
  		minn++;
	}
	return t;
}
 
int a[500001],b[500001],c[500001];
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int minl=2500000,minn=n;
	for(int i=1;i<=n;i++)a[i]=gondolaSeq[i-1];
	int loca=1,num=1;
	for(int i=1;i<=n;i++)if(0<a[i]&&a[i]<=n)
	{
		loca=i;
		num=a[i];
		i=n+1;
	}
	int m=n;int max=0;
	while(m>0)
	{
		if(loca>n)loca=1;
		if(num>n)num=1;
		b[num]=a[loca];
		if(max<b[num])max=b[num];
		loca++;
		num++;
		m--;
	}
 
//	for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++)if(b[i]==i)a[i]=0;else a[i]=i;
	for(int i=1;i<=n;i++)if(a[i]!=0)c[b[i]]=a[i];
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
//	for(int i=n+1;i<=max;i++)cout<<c[i]<<" ";cout<<endl;
	int x=0,last=0;
	for(int i=max;i>n;i--)if(c[i]!=0)
	{
//		cout<<";"<<i<<","<<x<<endl;
		int t;
		t=x;
		x=c[i];
		c[i]=t;
		if(i>last)last=i;
	}
	c[n]=x;
	
	for(int i=n+1;i<=max;i++)if(c[i]==0)c[i]=i;
//	for(int i=n;i<max;i++)cout<<c[i]<<" ";cout<<endl;
	for(int i=n;i<max;i++)replacementSeq[i-n]=c[i];
	
	return max-n;
}
 
int countReplacement(int n, int inputSeq[])
{
  return 1;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:34:6: warning: unused variable 'minl' [-Wunused-variable]
  int minl=2500000,minn=n;
      ^~~~
gondola.cpp:34:19: warning: unused variable 'minn' [-Wunused-variable]
  int minl=2500000,minn=n;
                   ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10