Submission #792275

#	Time	Username	Problem	Language	Result	Execution time	Memory
792275		MODDI	Gondola (IOI14_gondola)	C++17	25 / 100	9 ms	1108 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){
		vi arr(n);
		for(int i = 0; i < n; i++)	arr[i] = gondolaSeq[i];
		
		sort(arr.begin(), arr.end());
		int at = 1, j = 0, rez =0;
		for(int i = 0; i < n; i++){
			while(at < arr[i]){
				replacementSeq[j++] = at++;
				rez++; 
			}
			at++;
		}
		return rez;
	}
	else{
		set<int> active;
		map<int,int> replace;
		for(int i = 0; i < n; i++)	active.insert(gondolaSeq[i]);
		int at = gondolaSeq[pos];
		while(at <= n){
			at++;
			pos++;
			pos%=n;
		}
		int j = 0, rez = 0, need = 1;
		at=n+1;
		for(int i = pos; i < n; i++){
			replace[gondolaSeq[i]] = need++;
		}
		for(int i = 0; i < pos; i++)
			replace[gondolaSeq[i]] = need++;
		need=1;
		set<int> out;
		bool done[n+1];
		memset(done, false, sizeof done);
		for(int i = pos; i < n; i++){
			//cout<<"At: "<<i<<" "<<need<<" "<<gondolaSeq[i]<<" "<<at<<endl;
			if(gondolaSeq[i] == need){
				need++;
				continue;
			}
			else{
				if(!done[need]){
					replacementSeq[j++] = need;
					done[need++] = true;
					rez++;
				}
				while(at < gondolaSeq[i]){
					if(active.find(at) != active.end()){
						if(!done[replace[at]]){
							done[replace[at]] = true;
							replacementSeq[j++] = replace[at++];
							rez++;
						}
						else
							at++;
					}
					else{
						replacementSeq[j++] = at++;
						rez++;
					}
				}
			}
		}
		for(int i = 0; i < pos; i++){
			//cout<<"At: "<<i<<" "<<need<<" "<<gondolaSeq[i]<<" "<<at<<endl;
			if(gondolaSeq[i] == need){
				need++;
				continue;
			}
			else{
				if(!done[need]){
					replacementSeq[j++] = need;
					done[need++] = true;
					rez++;
				}
				while(at < gondolaSeq[i]){
					if(active.find(at) != active.end()){
						if(!done[replace[at]]){
							done[replace[at]] = true;
							replacementSeq[j++] = replace[at++];
							rez++;
						}
						else
							at++;
					}
					else{
						replacementSeq[j++] = at++;
						rez++;
					}
				}
			}
		}
		/*cout<<"NOT DONE: ";
		for(int i = 1; i <= n; i++){
			if(!done[i]){
				cout<<i<<" ";
			}
		}
		cout<<endl;
		cout<<"END: "<<at<<" "<<replace[at]<<" "<<done[replace[at]]<<endl;
		*/
		if(replace[at] != 0 && !done[replace[at]]){
			replacementSeq[j++] = replace[at];
			rez++;
		}
		return rez;
	}
}

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

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

• 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