Submission #430370

#	Time	Username	Problem	Language	Result	Execution time	Memory
430370		frodakcin	Gondola (IOI14_gondola)	C++11	100 / 100	86 ms	5956 KiB

gondola

#include "gondola.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <algorithm>

int valid(int n, int inputSeq[])
{
	std::map<int, int> map;
	for(int i=0;i<n;++i)
	{
		int x=inputSeq[i]-1;
		if(map.find(x) != map.end()) return 0;
		map.insert({x, i});
	}
	for(int i=0;i<n;++i)
		if(map.find(i)!=map.end() && map.find((i+1)%n)!=map.end())
		{
			int u=map[i], v=map[(i+1)%n];
			if(v != (u+1)%n)
				return 0;
		}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	for(int i=0;i<n;++i)
		if(gondolaSeq[i] <= n && gondolaSeq[i] != i+1)
		{
			std::rotate(gondolaSeq, gondolaSeq+(i-gondolaSeq[i]+1+n)%n, gondolaSeq+n);
		}
	std::map<int, int> map;
	for(int i=0;i<n;++i)
	{
		int x=gondolaSeq[i];
		assert(map.find(x) == map.end());
		map.insert({x, i});
	}
	int l=0, v=n;
	for(auto x:map)
		for(int t=x.second+1;v<x.first;)
			replacementSeq[l++]=t, t=++v;
	return l;
}

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

using ll = long long;
const int MOD = 1e9+9;

struct mint
{
	public:
		int v;
		mint(int _v=0): v(_v)
		{
			if(v < -MOD || MOD <= v) v%=MOD;
			if(v<0) v+=MOD;
		}

		mint& operator += (const mint& o) {if((v+=o.v)>=MOD) v-=MOD; return *this;}
		mint& operator -= (const mint& o) {if((v-=o.v)<0) v+=MOD;return *this;}
		mint& operator *= (const mint& o) {v=(ll)v*o.v%MOD; return *this;}

		friend mint operator + (mint a, const mint& b) {return a+=b;}
		friend mint operator - (mint a, const mint& b) {return a-=b;}
		friend mint operator * (mint a, const mint& b) {return a*=b;}

		template<typename T>
		friend mint pow(mint b, T p)
		{
			mint f(1);
			for(;p;p>>=1, b*=b)
				if(p&1)
					f*=b;
			return f;
		}
};

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq)) return 0;
	std::sort(inputSeq, inputSeq+n);
	mint ans(1);
	if(inputSeq[0] > n)
		ans *= mint(n);

	int v=n;
	for(int i=0;i<n;++i)
	{
		if(v < inputSeq[i])
			ans *= pow(mint(n-i), inputSeq[i]-v-1), v=inputSeq[i];
	}

	return ans.v;
}

• 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