Submission #99726

#	Time	Username	Problem	Language	Result	Execution time	Memory
99726		Retro3014	Gondola (IOI14_gondola)	C++17	55 / 100	1086 ms	5240 KiB

gondola

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

using namespace std;

typedef long long ll;

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+1;
		}
	}
	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;
}

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

const ll DIV = 1000000009;

ll multi(ll x, ll y){
	if(y==1)	return x%DIV;
	if(y==0)	return 1;
	ll m = multi(x, y/2);
	if(y%2==1)	return (((m*m)%DIV)*x)%DIV;
	return ((m*m)%DIV);
}



vector<int> v;

int countReplacement(int n, int inputSeq[]){
	if(!valid(n, inputSeq))	return 0;
	int mx = 0;
	for(int i=0; i<n; i++) mx = max(mx, inputSeq[i]);
	for(int i=0; i<n; i++){
		v.push_back(inputSeq[i]);
	}sort(v.begin(), v.end());
	bool tf = false;
	for(int i=0; i<n; i++){
		if(inputSeq[i]<=n){
			tf = true; break;
		}
	}
	ll ans = 1;
	if(!tf)	ans = n;
	int prv = n+1;
	ll t = n;
	for(int i=0; i<v.size(); i++){
		if(v[i]<=n)	{
			t--;
			continue;
		}
		ans = (ans * multi(t, v[i]-prv))%DIV;
		t--;
		prv = v[i]+1;
	}
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

• 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