Submission #754995

#	Time	Username	Problem	Language	Result	Execution time	Memory
754995		AngusRitossa	Gondola (IOI14_gondola)	C++14	100 / 100	43 ms	6812 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000009 
int occurance[100010];
int exists[300010];
unordered_set<int> existsSET;
int valid(int n, int inputSeq[])
{
	existsSET.clear();
	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] <= n) 
		{ 
			if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0;
			occurance[inputSeq[i]] = i;
			existsSET.insert(inputSeq[i]);
		}
		else if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0;
		else
		{
			existsSET.insert(inputSeq[i]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (existsSET.find(i) != existsSET.end())
		{
			int loc = occurance[i];
			for (int j = 1; j <= n; j++)
			{
				if (existsSET.find(j) != existsSET.end())
				{
					int diff = occurance[j] + n - loc;
					diff %= n;
					int diff2 = j-i;
					if (diff != diff2) return 0;
				}
			}
			return 1;
		}
	}

	return 1;
	
}

//----------------------
int hasToDestroy[300010];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	fill_n(exists, 300010, 0);
	pair<int, int> mx = { 0, 0 };
	int ans = 0;
	int firstloc = 1;
	for (int i = 0; i < n; i++)
	{
		exists[gondolaSeq[i]] = 1;
		occurance[gondolaSeq[i]] = i;
		mx = max(mx, { gondolaSeq[i], i } );
	}	
	for (int i = 1; i <= n; i++)
	{
		if (exists[i])
		{
			firstloc = occurance[i]+1-i;
			firstloc += n;
			firstloc %= n;
			break;
		}
	}
	for (int i = 0; i < n; i++)
	{
		int initiallyhere = (i-firstloc+n)%n;
		initiallyhere++;
		if (gondolaSeq[i] != initiallyhere) hasToDestroy[gondolaSeq[i]] = initiallyhere;
	}
	int initialmx = (mx.second - firstloc +n)%n;
	initialmx++;
	exists[mx.first] = false;
	queue<int> q;
	q.push(initialmx);
	for (int i = n+1; i < mx.first; i++)
	{
		if (!exists[i]) q.push(i);
	}
	for (int i = n+1; i <= mx.first; i++)
	{
		if (!exists[i])
		{
			replacementSeq[ans++] = q.front();
			q.pop();
		}
		else
		{
			replacementSeq[ans++] = hasToDestroy[i];
		}
	}
	return ans;
}
ll pow(ll n, ll k)
{
	if (k == 0) return 1;
	ll ans = pow(n, k/2);
	ans *= ans;
	ans %= mod;
	if (k % 2) ans *= n;
	return ans % mod;
}
//----------------------

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n, inputSeq)) return 0;
	ll ans = 1;
	vector<int> v;
	ll pre = n;
	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] > n) v.push_back(inputSeq[i]);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for (ll i = v.size()-1; i >= 0; i--)
	{
		ll at = v[i];
		ll dist = at-pre-1;
		//printf("%lld %lld\n", at, dist);
		if (dist)
		{
			ll mult = pow((i+1),dist);
			//printf("%lld %lld %lld\n", at, dist, mult);
			mult %= mod;
			ans *= mult;
			ans %= mod; 
		}
		pre = at;
	}
	if (v.size() == n) ans *= n;
	ans %= mod;
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:140:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |  if (v.size() == n) ans *= n;
      |      ~~~~~~~~~^~~~

• 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