Submission #120608

#	Time	Username	Problem	Language	Result	Execution time	Memory
120608		turbat	Gondola (IOI14_gondola)	C++14	100 / 100	128 ms	11508 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define N 2000005

map <int, int> pos, note;
int arr[N], mx, cnt, p;
bool can;
long long mod = 1e9 + 9, ans = 1;
vector <int> vc;

int valid(int n, int inputSeq[]){
	for (int i = 0;i < n;i++){
		if (mx < inputSeq[i]){
			mx = inputSeq[i];
			p = i;
		}
		pos[inputSeq[i]] = i;
		if (note[inputSeq[i]]) return 0;
		note[inputSeq[i]] = 1;
	}
	for (int i = 0;i < n;i++)
		if (inputSeq[i] <= n){
			can = 1;
			int now = inputSeq[i];
			arr[i] = now;
			for (int j = i + 1;j < n;j++){
				now++;
				if (now > n) now = 1;
				arr[j] = now;
			}
			for (int j = 0;j < i;j++){
				now++;
				if (now > n) now = 1;
				arr[j] = now;
			}
			break;
		}
	if (!can)
		for (int i = 0;i < n;i++)
			arr[i] = i + 1;
	int ok = 1;
	for (int i = 0;i < n;i++)
		if (inputSeq[i] <= n && inputSeq[i] != arr[i])
			ok = 0;
	return ok;
}


int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	if (!valid(n, gondolaSeq)) return 0;
	for (int i = 0;i < n;i++)
		if (gondolaSeq[i] > n)
			vc.push_back(gondolaSeq[i]);
	for (int i = n + 1;i <= mx;i++){
		if (!note[i]) {
			replacementSeq[i - n - 1] = arr[p];
			arr[p] = i;
		}
		else replacementSeq[i - n - 1] = arr[pos[i]];
	}
	return mx - n;
}

long long gg(long long x, int y){
	long long s = 1;
	while (y){
		if (y % 2) s = (s * x) % mod;
		x = (1ll * x * x) % mod;
		y /= 2;
	}
	return s;
}

int countReplacement(int n, int inputSeq[]){
	if (!valid(n, inputSeq)) return 0;
	if (!can) ans = n;
	for (int i = 0;i < n;i++)
		if (inputSeq[i] > n)
			vc.push_back(inputSeq[i]);
	sort(vc.begin(), vc.end());
	reverse(vc.begin(), vc.end());
	int bef = n;
	while (!vc.empty()){
		ans = (ans * gg(vc.size(), vc.back() - bef - 1)) % mod;
		bef = vc.back();
		vc.pop_back();
	}
	return ans;
}

• 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