Submission #292336

#	Time	Username	Problem	Language	Result	Execution time	Memory
292336		VodkaInTheJar	Gondola (IOI14_gondola)	C++14	100 / 100	65 ms	6008 KiB

gondola

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

const int maxn = 1e5 + 3; 

int valid(int n, int a[])
{
	set <int> s;
	for (int i = 0; i < n; i++)
	s.insert(a[i]);
	
	if ((int)s.size() < n)
	return 0;
	
	vector <int> v;
	for (int i = 0; i < n; i++)
	if (a[i] <= n)
	v.push_back(i);
	
	for (int i = 1; i < (int)v.size(); i++)
	{
		int val = a[v[0]] + v[i] - v[0];
		if (val > n)
		val -= n; 
		
		if (val != a[v[i]])
		return 0; 
	}
	
	return 1; 
}

int val[maxn];
int replacement(int n, int a[], int ans[])
{
	int pos = -1;
	for (int i = 0; i < n; i++)
	if (a[i] <= n)
	{
		pos = i;
		break;
	}
	
	if (pos == 1)
	for (int i = 0; i < n; i++)
	val[i] = i + 1; 
	
	else 
	{
		for (int i = pos + 1; i < n; i++)
		{
			val[i] = a[pos] + i - pos; 
			if (val[i] > n)
			val[i] -= n;
		}
		
		for (int i = 0; i < pos; i++)
		{
			val[i] = a[pos] + n - pos + i; 
			if (val[i] > n)
			val[i] -= n; 
		}
	}
	
	vector <pair <int, int> > v;
	for (int i = 0; i < n; i++)
	if (a[i] > n)
	v.push_back({a[i], i});
	
	sort (v.begin(), v.end());
	int last = n, len = 0;
	for (auto i: v)
	{
		for (int j = last + 1; j <= i.first; j++)
		{
			ans[len++] = val[i.second]; 
			val[i.second] = j; 
		}
		
		last = i.first; 
	}
	
	return len; 
}

const int mod = 1e9 + 9; 

int fast_pow(int x, int deg)
{
	int ans = 1, y = x;
	while (deg)
	{
		if (deg & 1)
		ans = 1ll * ans * y % mod;
		
		deg >>= 1;
		y = 1ll * y * y % mod; 
	}
	
	return ans;
}

int countReplacement(int n, int a[])
{
	if (!valid(n, a))
	return 0; 
	
	int ans = 1; 
	
	vector <int > v;
	for (int i = 0; i < n; i++)
	if (a[i] > n)
	v.push_back(a[i]);
	
	sort (v.begin(), v.end());
	int last = n;
	for (int i = 0; i < (int)v.size(); i++)
	{
		ans = 1ll * ans * fast_pow((int)v.size() - i, v[i] - last - 1) % mod;
		last = v[i]; 
	}
	
	bool is = false;
	for (int i = 0; i < n; i++)
	if (a[i] <= n)
	{
		is = true;
		break;
	}
	
	//assert(is != false); 
	
	if (!is)
	ans = 1ll * ans * n % mod; 
	
	return ans; 
}

/*
//const int maxn = 1e5 + 3; 

int n; 
int a[maxn]; 
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	cin >> a[i];
	
	cout << countReplacement(n, a) << endl; 
}
*/

• 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