제출 #611013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611013		penguinhacker	곤돌라 (IOI14_gondola)	C++17	90 / 100	19 ms	2860 KiB

gondola

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

void rot(vector<int>& a) {
	int n=a.size();
	for (int i=0; i<n; ++i)
		if (a[i]<=n) {
			int st=(i-(a[i]-1)+n)%n;
			rotate(a.begin(), a.begin()+st, a.end());
			break;
		}
}

int valid(int n, vector<int> a) {
	if (*min_element(a.begin(), a.end())>n)
		return 1;
	vector<int> b=a;
	sort(b.begin(), b.end());
	for (int i=0; i+1<n; ++i)
		if (b[i]==b[i+1])
			return 0;
	rot(a);
	for (int i=0; i<n; ++i)
		if (a[i]<=n&&a[i]!=i+1)
			return 0;
	return 1;
}

int valid(int n, int a[]) {
	return valid(n, vector<int>(a, a+n));
}

int replacement(int n, vector<int> a, int b[]) {
	assert(valid(n, a));
	rot(a);
	int mx=*max_element(a.begin(), a.end());
	vector<int> who(mx+1, -1);
	for (int i=0; i<n; ++i)
		who[a[i]]=i;
	vector<int> seq(n);
	iota(seq.begin(), seq.end(), 1);
	for (int i=n+1; i<=mx; ++i) {
		int pos=who[i]!=-1?who[i]:who[mx];
		b[i-n-1]=seq[pos];
		seq[pos]=i;
	}
	return mx-n;
}

int replacement(int n, int a[], int b[]) {
	return replacement(n, vector<int>(a, a+n), b);
}

const int M=1e9+9;

#define ll long long

ll bp(ll b, int p) {
	ll r=1;
	for (; p; p/=2, b=b*b%M)
		if (p%2)
			r=r*b%M;
	return r;
}

int countReplacement(int n, vector<int> a) {
	if (!valid(n, a))
		return 0;
	rot(a);
	int free=0;
	vector<int> pos;
	for (int i : a) {
		if (i>n) {
			++free;
			pos.push_back(i);
		}
	}
	sort(pos.begin(), pos.end());
	int last=n;
	ll ans=1;
	for (int i : pos) {
		ans=ans*bp(free--, i-last-1)%M;
		last=i;
	}
	if (*min_element(a.begin(), a.end())>n)
		ans=ans*n%M;
	return ans;
}

int countReplacement(int n, int a[]) {
	return countReplacement(n, vector<int>(a, a+n));
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 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