Submission #65288

#	Time	Username	Problem	Language	Result	Execution time	Memory
65288		gnoor	Gondola (IOI14_gondola)	C++17	55 / 100	28 ms	4440 KiB

gondola

#include "gondola.h"

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool mark[300100];

int valid(int n, int inputSeq[])
{
	int key=-1;
	int id=-1;
	int cur;
	for (int i=0;i<n;i++) {
		inputSeq[i]--;
		if (mark[inputSeq[i]]) return 0;
		mark[inputSeq[i]]=true;
	}
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>=n) continue;
		key=inputSeq[i];
		id=i;
	}
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>=n) continue;
		cur=key+i-id;
		cur%=n;
		cur+=n;
		cur%=n;
		if (inputSeq[i]!=cur) return 0;
	}
	return 1;
}

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

int init[100100];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int id=0;
	int key=1;
	for (int i=0;i<n;i++) {
		if (gondolaSeq[i]>n) continue;
		id=i;
		key=gondolaSeq[i];
		break;
	}
	init[id]=key;
	for (int i=id+1;i<n;i++) {
		init[i]=init[i-1]+1;
		if (init[i]>n) init[i]-=n;
	}
	for (int i=id-1;i>=0;i--) {
		init[i]=init[i+1]-1;
		if (init[i]<=0) init[i]+=n;
	}

	vector<pair<int,int>> ei;
	for (int i=0;i<n;i++) {
		if (gondolaSeq[i]<=n) continue;
		ei.push_back({gondolaSeq[i],i});
	}
	sort(ei.begin(),ei.end());

	int sz=0;
	int curid=0;
	int curcar=n+1;
	int curgon=0;
	for (int i=0;i<(int)ei.size();i++) {
		while (curcar<ei[i].first) {
			while (init[curgon]==gondolaSeq[curgon]) curgon++;
			replacementSeq[sz++]=init[curgon];
			init[curgon]=curcar;
			curcar++;
		}
		replacementSeq[sz++]=init[ei[i].second];
		init[ei[i].second]=ei[i].first;
		curcar++;
	}
	return sz;
}

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

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

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:69:6: warning: unused variable 'curid' [-Wunused-variable]
  int curid=0;
      ^~~~~

• 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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10