제출 #1280222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280222		Nurislam	곤돌라 (IOI14_gondola)	C++20	90 / 100	154 ms	327680 KiB

gondola

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

using namespace std;

int valid(int n, int in[])
{
	vector<int> a;
	for(int i = 0; i < n; i ++ ) if(in[i] < n)a.push_back(in[i]);
	set<int> st;
	
	for(int i = 0; i < n; i ++ ) st.insert(in[i]);
	if(st.size() != n) return 0;
	
	
	int cnt = 0;
	for(int i = 0; i < a.size(); i ++ ) {
		if(a[i] > a[(i+1)%a.size()]) cnt ++ ;
	};
	return (cnt == 1 || a.empty());
}

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

int replacement(int n, int gs[], int rs[])
{
	int mx = n;
	for(int i = 0; i < n; i ++ ) {
		mx = max(mx, gs[i]);
	};
	int sz = mx - n;
	vector<int> us(mx+1);
	for(int i = 0; i < n; i ++ ) {
		us[gs[i]] = 1;
	};
	
	vector<int> in(n);
	for(int i = 0; i < n; i ++ ) {
		if(gs[i] <= n) {
			for(int j = i - 1; j >= 0; j -- ) {
				if(gs[i] - (i-j) <= 0) in[j] = gs[i] - (i-j) + n;
				else in[j] = gs[i] - (i-j);
			};
			for(int j = i; j < n; j ++ ) {
				if(gs[i] + (j-i) > n) in[j] = gs[i] + (j-i) - n;
				else in[j] = gs[i] + (j-i);
			};
			break;
		};
	};
	if(in[0] == 0) {
		for(int i = 0; i < n; i ++ ) {
			in[i] = i+1;
		};
	};
	
	for(int i = 0; i < n; i ++ ) {
		if(in[i] < gs[i]) {
			rs[gs[i]-n-1] = in[i];
		};
	};
	
	for(int i = sz-1; i >= 0; i -- ) {
		if(rs[i] == 0) {
			int x = rs[i+1];
			rs[i+1] = n + i + 1;
			rs[i] = x;
		};
	};
	return sz;
}

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

int countReplacement(int n, int gs[])
{
	
	vector<int> a;
	for(int i = 0; i < n; i ++ ) if(gs[i] < n)a.push_back(gs[i]);
	
	
	int cnt = 0;
	for(int i = 0; i < a.size(); i ++ ) {
		if(a[i] > a[(i+1)%a.size()]) cnt ++ ;
	};
	if(cnt != 1 && a.size()) return 0;
	
	bool o1 = 1;
	for(int i = 0; i < n; i ++ ) {
		if(gs[i] > n) o1 = 0;
	};
	if(o1) return 1;
	
	/////////////////////////////////////////////////////////////////////
	
	int mx = n;
	for(int i = 0; i < n; i ++ ) {
		mx = max(mx, gs[i]);
	};
	vector<int> us(mx+1);
	for(int i = 0; i < n; i ++ ) {
		us[gs[i]] = 1;
	};
	
	vector<int> in(n);
	for(int i = 0; i < n; i ++ ) {
		if(gs[i] <= n) {
			for(int j = i - 1; j >= 0; j -- ) {
				if(gs[i] - (i-j) <= 0) in[j] = gs[i] - (i-j) + n;
				else in[j] = gs[i] - (i-j);
			};
			for(int j = i; j < n; j ++ ) {
				if(gs[i] + (j-i) > n) in[j] = gs[i] + (j-i) - n;
				else in[j] = gs[i] + (j-i);
			};
			break;
		};
	};
	bool rp = 0;
	if(in[0] == 0) {
		rp = 1;
		for(int i = 0; i < n; i ++ ) {
			in[i] = i+1;
		};
	};
	
	//for(int i = 0; i < n; i ++ ) {
		//cout << in[i] << '\n';
	//};
	
	vector<int> ps{0};
	for(int i = 0; i < n; i ++ ) 
		if(in[i] < gs[i]) 
			ps.push_back(gs[i]-n);
	
	long long ans = 1, mod = 1e9+9;
	sort(ps.rbegin(), ps.rend());
	
	//for(int i : ps) cout << i << ' ';
	//cout << '\n';
	function<long long(int,int)> bp =[&](int a, int n) {
		if(n == 0) return 1ll;
		long long b = bp(a, n >> 1);
		if(n & 1) return b*b%mod*a %mod;
		return b*b%mod;
	};
	for(int i = 0; i+1 < ps.size(); i ++ ) {
		ans *= bp(i+1, ps[i] - ps[i+1]-1);
		ans %= mod;
	};
	
	if(rp)ans = ans * n %mod;
	int ans2 = ans;
	
	return ans2;
	
}

• 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: 0 / 10