제출 #1281561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281561		Jawad_Akbar_JJ	곤돌라 (IOI14_gondola)	C++17	100 / 100	48 ms	6000 KiB

gondola

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "gondola.h"

using namespace std;

int valid(int n, int seq[]){
	map<int,int> mp;
	for (int i=0;i<n;i++){
		if (mp.find(seq[i]) != mp.end())
			return 0;
		mp[seq[i]];
	}

	vector<int> vc(n + 1);
	for (int i=0;i<=n;i++){
		if (i == n)
			return 1;
		if (seq[i] <= n){
			for (int j=i;j<i + n;j++)
				vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
			break;
		}
	}

	for (int i=1;i<=n;i++)
		if (vc[i] <= n and vc[i] != i)
			return 0;
	return 1;
}

int replacement(int n, int seq[], int ans[]){
	vector<int> vc(n + 1);
	vector<pair<int,int>> vc2;

	for (int i=0;i<=n;i++){
		if (i == n){
			for (int j=0;j<n;j++)
				vc[j+1] = seq[j];
		}
		else if (seq[i] <= n){
			for (int j=i;j<i + n;j++)
				vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
			break;
		}
	}

	for (int i=1;i<=n;i++){
		if (vc[i] > n)
			vc2.push_back({vc[i], i});
	}
	sort(begin(vc2), end(vc2));

	int cur = n + 1, sz = 0;
	for (auto [vl, id] : vc2){
		// cout<<cur<<" "<<vl<<" "<<id<<endl;
		while (cur < vl)
			ans[sz++] = id, id = cur++;
		ans[sz++] = id;
		cur++;
	}
	return sz;
}

int mod = 1e9 + 9;

int power(int a, int b){
	if (b == 0)
		return 1;
	int ans = power(a, b / 2);
	ans = 1LL * ans * ans % mod;
	if (b % 2)
		ans = 1LL * ans * a % mod;
	return ans;
}

int countReplacement(int n, int seq[]){
	if (valid(n, seq) == 0)
		return 0;
	vector<int> vc(n + 1);
	vector<pair<int,int>> vc2;

	for (int i=0;i<=n;i++){
		if (i == n){
			for (int j=0;j<n;j++)
				vc[j+1] = seq[j];
		}
		else if (seq[i] <= n){
			for (int j=i;j<i + n;j++)
				vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
			break;
		}
	}

	for (int i=1;i<=n;i++){
		if (vc[i] > n)
			vc2.push_back({vc[i], i});
	}
	sort(begin(vc2), end(vc2));

	int lst = n, Ways = 1 + (n - 1) * (vc2.size() == n);
	for (int i=0;i<vc2.size();i++){
		auto [vl, id] = vc2[i];
		int k = vl - lst;
		Ways = 1LL * Ways * power(vc2.size() - i, k - 1) % mod;
		lst = vl;
	}
	return Ways;
}

• 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