Submission #1271306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271306		WH8	곤돌라 (IOI14_gondola)	C++20	100 / 100	44 ms	6580 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
typedef long long ll;
using namespace std;

signed valid(signed n, signed inputSeq[])
{
	set<int> s;
	int num=-1;
	for(int i=0;i<n;i++){
		if(s.find(inputSeq[i])!=s.end())return 0;
		s.insert(inputSeq[i]);
		int cur=(inputSeq[i]-i < 0 ? inputSeq[i]-i+n:inputSeq[i]-i);
		if(inputSeq[i] <= n){
			if(num == -1){
				num=cur;
			}
			else {
				if(num!=cur){
					return 0;
				}
			}
		}
	}
	return 1;
}

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

signed replacement(signed N, signed gondolaSeq[], signed replacementSeq[])
{
	long long n=N;
	vector<pair<int,int>> t;
	int st=0;
	for(int i=0;i<n;i++){
		if(gondolaSeq[i]<=n){
			int one=(i-gondolaSeq[i]+1);
			if(one < 0)one+=n;
			st=one;
			break;
		}
	}
	for(int i=0, j=st;i<n;i++){
		t.push_back({i+1, gondolaSeq[(i+j)%n]});
	}
	sort(t.begin(),t.end(), [&](auto a, auto b){
		return a.s<b.s;
	});
	assert((int)t.size()==n);
	int ind=0;
	for(int i=0;i<n;i++){
		if(t[i].f==t[i].s)continue;
		replacementSeq[ind++]=t[i].f;
		int prv;
		if(i==0)prv=n;
		else prv=max(t[i-1].s, n);
		for(int j=prv+1;j<t[i].s;j++){
			replacementSeq[ind++]=j;
		}
	}
	return ind;
}

//----------------------
const ll mod=1000000009;

ll exp(ll x, ll k){
	if(k==0)return 1;
	if(k==1)return x % mod;
	ll res=exp(x, k/2);
	if(k%2==0)return res * res % mod;
	else return res * res %mod * x %mod;
}
signed countReplacement(signed N, signed gondolaSeq[])
{
	int n=N;
	int mn=1e15;
	for(int i=0;i<n;i++)mn=min(mn,(int)gondolaSeq[i]);
	//~ cout<<exp(3, 78)<<"\n";
	vector<pair<int,int>> t;
	int st=0;
	for(int i=0;i<n;i++){
		if(gondolaSeq[i]<=n){
			int one=(i-gondolaSeq[i]+1);
			if(one < 0)one+=n;
			st=one;
			break;
		}
	}
	for(int i=0, j=st;i<n;i++){
		t.push_back({i+1, gondolaSeq[(i+j)%n]});
	}
	sort(t.begin(),t.end(), [&](auto a, auto b){
		return a.s<b.s;
	});
	assert((int)t.size()==n);
	if(!valid(n, gondolaSeq))return 0;
	ll ans=1;
	for(int i=0;i<n;i++){
		if(t[i].f==t[i].s)continue;
		int prv;
		if(i == 0)prv=n;
		else prv=max(n, t[i-1].s);
		int x=t[i].s-prv-1;
		//~ printf("dist %lld, choices %lld\n", x, n-i);
		ans=ans*exp(n-i, x)%mod;
		//~ ans=ans*exp(n-i, x)%mod;
	}
	if(mn>n)ans=ans*n%mod;
	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