Submission #792961

#	Time	Username	Problem	Language	Result	Execution time	Memory
792961		MODDI	Gondola (IOI14_gondola)	C++14	75 / 100	15 ms	2332 KiB

gondola

#include "gondola.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
int valid(int n, int inputSeq[])
{
	int pos = -1;
	for(int i = 0; i < n; i++){
		if(inputSeq[i] == 1){
			pos = i;
			break;
		}
	}
	bool seq = true;
	int at = 1, lim = pos;
	while(pos < n){
		if(inputSeq[pos] == at){
			pos++;
			at++;
		}
		else{
			seq = false;
			break;
		}
	}
	if(!seq)	return 0;
	pos = 0;
	while(pos < lim){
		if(inputSeq[pos] == at){
			pos++;
			at++;
		}
		else{
			seq = false;
			break;
		}
	}
	if(!seq) return 0;
	return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int pos = -1;
	for(int i = 0; i < n; i++){
		if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){
			pos = i;
			break;
		}
	}
	if(pos == -1){
		vector<pii> arr(n);
		for(int i = 0; i < n; i++){
			arr[i] = mp(gondolaSeq[i], i);
		}
		sort(arr.begin(), arr.end());
		int j = 0, rez = 0, here = 1, at = n + 1;
		int pos = arr[0].second, need[n];
		for(int i = pos; i < n; i++)	need[i] = here++;
		for(int i = 0; i < pos; i++)	need[i] = here++;
		for(int i = 0; i < (int)arr.size(); i++){
			int where = arr[i].second, val = arr[i].first;
			replacementSeq[j++] = need[where];
			rez++;
			while(at < val){
				replacementSeq[j++] = at++;
				rez++;
			}
			at++;
		}
		return rez;
	}
	else{
		int need[n];
		bool done[n+1];
		memset(done, false, sizeof done);
		int at = gondolaSeq[pos];
		while(at <= n){
			at++;
			pos++; pos%=n;
		}
		int here = 1;
		for(int i = pos; i < n; i++)	need[i] = here++;
		for(int i = 0; i < pos; i++)	need[i] = here++;
		vector<pii> arr;
		for(int i = 0; i < n; i++){
			if(need[i] == gondolaSeq[i])	done[need[i]] = true;
			else{
				arr.pb(mp(gondolaSeq[i], i));
			}
		}
		sort(arr.begin(), arr.end());
		at = n + 1;
		int j = 0, rez = 0;
		for(int i = 0; i < (int)arr.size(); i++){
			int where = arr[i].second, val = arr[i].first;
			replacementSeq[j++] = need[where];
			rez++;
			while(at < val){
				replacementSeq[j++] = at++;
				rez++;
			}
			at++;
		}
		return rez;
	}
}
const int mod = 1e9 + 9;
int countReplacement(int n, int inputSeq[])
{
	//int checker = valid(n, inputSeq);
	vector<pii> arr;
	int pos = -1;
	for(int i = 0; i < n; i++){
		arr.pb(mp(inputSeq[i], i));
		if(inputSeq[i] >= 1 && inputSeq[i] <= n)	pos = i;
	}
	if(pos == -1)	assert(false);
	int at = inputSeq[pos];
	while(at <= n){
		at++;
		pos++;
		pos%=n;
	}
	int skipped = 0;
	at=1;
	bool ok = true;
	for(int i = pos; i < n; i++){
		if(inputSeq[i] == at+skipped){
			at++;
			skipped = 0;
		}
		else if(inputSeq[i] <= n && at + skipped > inputSeq[i]){
			ok = false;
		}
		else
			skipped++;
	}
	//cout<<"OK: "<<ok<<endl;
	if(!ok)	return 0;
	bool sub1 = true;
	for(int i = 0; i < n; i++){
		if(inputSeq[i] >= 1 && inputSeq[i] <= n + 3)	continue;
		else sub1 = false;
	}
	if(n > 50)	sub1 = false;
	if(sub1){
		bool n1 = false, n2 = false, n3 = false;
		for(int i = 0; i < n; i++){
			if(inputSeq[i] == n+1)	n1 = true;
			if(inputSeq[i] == n+2) 	n2 = true;
			if(inputSeq[i] == n+3)	n3 = true;
		}
		if(!n1 && n2 && n3)	return 2;
		else 	return 1;
	}
	else if(n <= 50){
		//cout<<"HERE: "<<endl;
		ll ways = 1;
		int at = n+1;
		while(at <= 100){
			bool ima = false;
			for(int i = 0; i < n; i++){
				if(inputSeq[i] == at)	ima = true;
			}
			if(ima)	at++;
			else{
				int cnt = 0;
				for(int i = 0; i < n; i++){
					if(inputSeq[i] > at)	cnt++;
				}
				if(cnt ==0)	break;
				ways *= cnt;
				ways %= mod;
				at++;
			}
		}
		return (int)ways;
	}
	return -3;
}

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