Submission #541463

#	Time	Username	Problem	Language	Result	Execution time	Memory
541463		Mdominykas	Gondola (IOI14_gondola)	C++14	Compilation error	0 ms	0 KiB

gondola

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

int valid(int n, int inputSeq[])
{
	set<int> difCount;

	for(int i = 0; i < n; i++)
 	{
 		if(inputSeq[i] <= n)
 		{
 			difCount.insert((inputSeq[i] + n - i - 1) % n);
 		}
 	}

 	vector<int> sortedSeq;
 	for(int i = 0; i < n; i++)
 		sortedSeq.push_back(inputSeq[i]);

 	sort(sortedSeq.begin(), sortedSeq.end());
 	sortedSeq.erase(unique(sortedSeq.begin(), sortedSeq.end()), sortedSeq.end());

 	if(sortedSeq.size() != n)
 		return 0;

 	if(difCount.size() > 0)
 	{
 		assert(*difCount.rbegin() < n);
 	}
 	if(difCount.size() > 1)
 		return 0;
 	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	assert(n != 0);
	if(!valid(n, gondolaSeq))
		return 0;

	vector<int> current, goal;
	for(int i = 0; i < n; i++)
	{
		goal.push_back(gondolaSeq[i]);
		current.push_back(i + 1);
	}

	int diff = 0;
	for(int i = 0; i < n; i++)
	{
		if(gondolaSeq[i] <= n)
		{
			diff = gondolaSeq[i] - (i + 1);
			break;
		}
	}

	// cout << "diff = " << diff << endl;

	for(int i = 0; i < n; i++)
	{
		current[i] += diff;
		if(current[i] > n)
			current[i] -= n;
		if(current[i] <= 0)
			current[i] += n;
	}

	vector<pair<int, int> > sortedGoal;
	for(int i = 0; i < n; i++)
	{
		if(goal[i] > n)
			sortedGoal.push_back(make_pair(goal[i], i));
	}

	sort(sortedGoal.begin(), sortedGoal.end());

	int l = 0;

	int cur = n + 1;

	for(int i = 0; i < sortedGoal.size(); i++)
	{
		while(current[sortedGoal[i].second] < sortedGoal[i].first)
		{
			replacementSeq[l] = current[sortedGoal[i].second];
			l++;
			current[sortedGoal[i].second] = cur;
			cur++;
		}
	}

	// cout << "gale l yra: " << l << endl;
	return l;
}

long long mod = 1000000009;

long long modPow(long long a, long long n)
{
	if(n == 0)
		return 1;
	else if (n % 2 == 0)
	{
		long long part = modPow(a, n / 2);
		return (part * part) % mod;
	}
	else
	{
		return (a * modPow(a, n - 1)) % mod;
	}
}

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

int countReplacement(int n, int inputSeq[])
{
	if(valid(n, inputSeq) == 0)
		return 0;

	int diff = -5 * n;
	for(int i = 0; i < n; i++)
	{
		if(inputSeq[i] <= n)
		{
			diff = inputSeq[i] - (i + 1);
			break;
		}
	}

	bool everyPos = false;
	if(diff == -5 * n)
		everyPos = true;

	vector<int> sortedGoal;
	for(int i = 0; i < n; i++)
	{
		if(inputSeq[i] > n)
			sortedGoal.push_back(inputSeq[i]);
	}

	sort(sortedGoal.begin(), sortedGoal.end());

	int cur = n + 1;
	long long ans = 1;

	for(int i = 0; i < sortedGoal.size(); i++)
	{
		// cout << "keliu: " << (int) sortedGoal.size() - i << " " << sortedGoal[i] - cur << endl; 
		ans *= modPow((int)sortedGoal.size() - i, sortedGoal[i] - cur);
		ans %= mod;
		cur = sortedGoal[i] + 1;
	}

	if(everyPos)
	{
		ans *= (long long) n;
		ans %= mod;
	}

	return ans;

}

Compilation message (stderr)

gondola.cpp:2:10: fatal error: grader.h: No such file or directory
    2 | #include "grader.h"
      |          ^~~~~~~~~~
compilation terminated.