Submission #127810

#	Time	Username	Problem	Language	Result	Execution time	Memory
127810		zozder	Gondola (IOI14_gondola)	C++14	35 / 100	16 ms	1660 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[250001],b[250001],c[150001];

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int minl=10000,minn=n;
	for(int i=1;i<=n;i++)a[i]=gondolaSeq[i-1];
	for(int i=1;i<=n;i++)if(a[i]<minn&&0<a[i]&&a[i]<=n)
	{
		minn=a[i];
		minl=i;
	}
	int m=n;int max=0;
	while(m>0)
	{
		if(minl>n)minl=1;
		b[n-m+1]=a[minl];
		if(max<b[n-m+1])max=b[n-m+1];
		minl++;
		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]-n]=a[i];
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
	int len=max-n;
//	for(int i=1;i<=len;i++)cout<<c[i]<<" ";cout<<endl;
	int x=0,last=0;
	for(int i=len;i>0;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[0]=x;
	
	for(int i=1;i<=len;i++)if(c[i]==0)c[i]=i+n;
//	for(int i=0;i<last;i++)cout<<c[i]<<" ";cout<<endl;
	for(int i=0;i<last;i++)replacementSeq[i]=c[i];
	
	return last;
}

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

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