Submission #94469

#	Time	Username	Problem	Language	Result	Execution time	Memory
94469		fjzzq2002	Gondola (IOI14_gondola)	C++14	100 / 100	105 ms	6904 KiB

gondola

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

int valid(int n,int x_[])
{
	static int x[100001];
	set<int> u;
	int s=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1; u.insert(x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	if(int(u.size())!=n) return 0;
	for(int i=0;i<n;++i)
		if(x[i]<n&&(s+i)%n!=x[i]) return 0;
	return 1;
}

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

int replacement(int n, int x_[], int o[])
{
	static int x[100001],y[100001];
	set<int> em;
	map<int,int> t;
	int s=0,mx=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1;
		t[x[i]]=i; mx=max(mx,x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	for(int i=0;i<n;++i)
	{
		y[i]=(s+i)%n;
		if(y[i]!=x[i]) em.insert(i);
	}
	int on=0;
	for(int j=n;j<=mx;++j)
	{
		int p;
		if(t.count(j))
			em.erase(p=t[j]);
		else p=*em.begin();
		o[on++]=y[p]+1; y[p]=j;
	}
	return on;
}

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

#define fi first
#define se second
const int MOD=1e9+9;
typedef long long ll;
ll qp(ll a,ll b)
{
	ll x=1; a%=MOD;
	while(b)
	{
		if(b&1) x=x*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return x;
}

int countReplacement(int n, int x_[])
{
	if(!valid(n,x_)) return 0;
	static int x[100001],y[100001];
	map<int,int> sb;
	int s=n,mx=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1; mx=max(mx,x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	for(int i=0;i<n;++i)
	{
		y[i]=(s+i)%n;
		if(y[i]!=x[i]) sb[x[i]]--;
	}
	int ini=sb.size();
	sb[mx+1]=0;
	sb[n-1]+=ini;
	ll ans=1;
	int su=0;
	for(auto t=sb.begin();;++t)
	{
		if(t->fi>mx) break;
		su+=t->se;
		auto u=t; ++u;
		ans=ans*qp(su,u->fi-t->fi-1)%MOD;
	}
	if(s==n) ans=ans*(ll)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