제출 #120584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120584		turbat	곤돌라 (IOI14_gondola)	C++14	45 / 100	23 ms	2688 KiB

gondola

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

int arr[N], mx, pos[3 * N], cnt, p;
bool note[3 * N];
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){
			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;
		}
	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[]){
	ans = 1;
	if (!valid(n, inputSeq)) return 0;
	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: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10