Submission #65306

#	Time	Username	Problem	Language	Result	Execution time	Memory
65306		gnoor	Gondola (IOI14_gondola)	C++17	100 / 100	111 ms	7548 KiB

gondola

#include "gondola.h"

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

using namespace std;


set<int> mark;

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.find(inputSeq[i])!=mark.end()) return 0;
		mark.insert(inputSeq[i]);
	}
	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 mod=1000000009;

long long poww(long long b,int x) {
	if (x==0) return 1;
	if (x==1) return b;
	long long tmp=poww(b,x/2);
	tmp*=tmp;
	tmp%=mod;
	if (x%2) return (tmp*b)%mod;
	return tmp;
}

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n,inputSeq)) return 0;
	for (int i=0;i<n;i++) inputSeq[i]++;
	int id=0;
	int key=1;
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>n) continue;
		id=i;
		key=inputSeq[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<int> ei;
	for (int i=0;i<n;i++) {
		if (inputSeq[i]<=n) continue;
		ei.push_back(inputSeq[i]);
	}
	sort(ei.begin(),ei.end());
	int curcar=n+1;
	int cnt=ei.size();
	long long ans=1;
	if (cnt==n) ans=n;
	for (int i=0;i<(int)ei.size();i++) {
		ans*=poww(cnt,ei[i]-curcar);
		ans%=mod;
		curcar=ei[i]+1;
		cnt--;
	}
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:71: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: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10