Submission #99645

#	Time	Username	Problem	Language	Result	Execution time	Memory
99645		Retro3014	Gondola (IOI14_gondola)	C++17	25 / 100	1079 ms	4856 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_X = 250000;

set<int> st;

int valid(int n, int inputSeq[]){
	int s = -1;
	for(int i=0; i<n; i++){
		if(st.find(inputSeq[i])!=st.end())	return false;
		st.insert(inputSeq[i]);
	}
	for(int i=0; i<n; i++){
		if(inputSeq[i]<=n){
			s = i; break;
		}
	}
	if(s==-1)	return 1;
	int idx = s, now = inputSeq[idx];
	bool tf = true;
	while(1){
		if(inputSeq[idx]<=n && inputSeq[idx]!=now){
			tf = false;
			break;
		}
		if(idx==(s+n-2)%n+1)	break;
		now = now%n+1; idx = (idx+1)%n;
	}
	if(tf)	return 1;
	tf = true;
	idx = s; now = inputSeq[idx];
	while(1){
		if(inputSeq[idx]<=n &&inputSeq[idx]!=now){
			tf = false;
			break;
		}
		if(idx==s%n+1)	break;
		idx = (idx+n-1)%n; now = (now+n-2)%n+1;
	}
	if(tf)	return 1;
	return 0;
}

//----------------------

int loc[MAX_X+1];
int num[MAX_X+1];

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int mx = 0;
	for(int i=0; i<n; i++) mx = max(mx, gondolaSeq[i]);
	for(int i=1; i<=mx; i++)	loc[i] = -1;
	for(int i=0; i<n; i++)	loc[gondolaSeq[i]] = i;
	int s = -1;
	for(int i=0; i<n; i++){
		if(gondolaSeq[i]<=n){
			s = i; break;
		}
	}
	if(s==-1){
		for(int i=0; i<n; i++){
			num[i] = i;
		}
	}
	else{
		bool tf = true;
		int idx = s, now = gondolaSeq[idx];
		while(1){
			if(gondolaSeq[idx]<=n && gondolaSeq[idx]!=now){
				tf = false; break;
			}
			idx = idx%n+1; now = now%n+1;
			if(idx==s)	break;
		}
		if(tf){
			idx = s; now = gondolaSeq[idx];
			while(1){
				num[idx] = now;
				idx = (idx+1)%n; now = now%n+1;
				if(idx==s)	break;
			}
		}else{
			idx = s; now = gondolaSeq[idx];
			while(1){
				num[idx] = now;
				idx = (idx+n-1)%n; now = (now+n-2)%n+1;
				if(idx==s)	break;
			}
		}
	}
	int idx = 0;
	int cnt = 0;
	for(int i=n+1; i<=mx; i++){
		if(loc[i]!=-1){
			replacementSeq[cnt++] = num[loc[i]];
			num[loc[i]] = i;
		}else{
			while(gondolaSeq[idx]==num[idx])	idx++;
			replacementSeq[cnt++] = num[idx];
			num[idx] = i;
		}
	}
	return cnt;
}

//----------------------

int countReplacement(int n, int inputSeq[]){
	if(!valid(n, inputSeq))	return 0;

}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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