Submission #131350

#	Time	Username	Problem	Language	Result	Execution time	Memory
131350		MAMBA	Gondola (IOI14_gondola)	C++17	55 / 100	33 ms	4216 KiB

gondola

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

using namespace std;

#define rep(i, j , k) for(int i = j; i < (int) k; i++)

typedef vector<int> vi;

const int N = 3e5 + 10;

int pos[N];

int valid(int n, int A[])
{
	memset(pos , -1, sizeof(pos));
	rep(i , 0 , n) {
		A[i]--;
		if (~pos[A[i]]) return 0;
		pos[A[i]] = i;
	}

	int last = -1;
	rep(i , 0 , n) 
		if(~pos[i]) {
			if (!~last) {
				last = i;
				continue;
			}
			if ((i - last) != (pos[i] - pos[last] + n) % n)
				return 0;
		}
	return 1;
}

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

int lo[N];
set<int> st;

int replacement(int n, int A[], int B[])
{
	st.clear();
	memset(pos , -1, sizeof(pos));
	int mx = -1;
	rep(i , 0 , n) {
		pos[A[i]] = i;
		mx = max(mx , A[i]);
	}

	bool flag = false;
	rep(i , 1 , n + 1) 
		if (~pos[i]) {
			rep(j , 1 , n + 1) {
				lo[(pos[i] + j - i + n) % n] = j;
				if(!~pos[j])
					st.insert((pos[i] + j - i + n) % n);
			}
			flag = true;
			break;
		}
	if (!flag) 
		rep(i , 1 , n + 1) {
			lo[i - 1] = i;
			st.insert(i - 1);
		}

	int L = 0;
	rep(i , n + 1, mx + 1) {
		if (~pos[i]) {
			B[L++] = lo[pos[i]];
			st.erase(pos[i]);
		}
		else {
			int v = *st.begin();
			B[L++] = lo[v];
			lo[v] = i;
		}
	}	
	return L;

}

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

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