Submission #371269

#	Time	Username	Problem	Language	Result	Execution time	Memory
371269		peijar	Gondola (IOI14_gondola)	C++17	100 / 100	221 ms	6124 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

int valid(int n, int inputSeq[])
{
	set<int> seen;
	for (int i(0); i < n; ++i)
	{
		if (seen.count(inputSeq[i]))
			return 0;
		seen.insert(inputSeq[i]);
	}
	for (int i(0); i < n; ++i)
		if (inputSeq[i] <= n)
		{
			for (int j(1); j < n; ++j)
				if (inputSeq[(i+j)%n] <= n and inputSeq[(i+j)%n]%n != (inputSeq[i] + j)%n)
					return 0;
			return 1;
		}
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	assert(valid(n, gondolaSeq));
	
	int posNormal(0);
	while (posNormal < n and gondolaSeq[posNormal] > n)
		posNormal++;
	if (posNormal != n)
		rotate(gondolaSeq, gondolaSeq + (posNormal - gondolaSeq[posNormal]+1+n)%n, gondolaSeq + n);
	vector<pair<int, int>> toReplace;
	for (int i(0); i < n; ++i)
		if (gondolaSeq[i] > n)
			toReplace.emplace_back(gondolaSeq[i]-n, i+1);
	sort(toReplace.begin(), toReplace.end());
	int curLen(0);
	for (auto [val, id] : toReplace)
		while (curLen < val)
		{
			replacementSeq[curLen++] = id;
			id = curLen+n;
		}
  return curLen;
}

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

template<const int32_t MOD>
struct ModInt {
	long long x;
	ModInt() : x(0) {}
	ModInt(long long u) : x(u) { x %= MOD; if (x < 0) x += MOD;}
	friend bool operator == (const ModInt& a, const ModInt& b) { return a.x == b.x; }
	friend bool operator != (const ModInt& a, const ModInt& b) { return a.x != b.x; }
	friend bool operator < (const ModInt& a, const ModInt& b) { return a.x < b.x; }
	friend bool operator > (const ModInt& a, const ModInt& b) { return a.x > b.x; }
	friend bool operator <= (const ModInt& a, const ModInt& b) { return a.x <= b.x; }
	friend bool operator >= (const ModInt &a, const ModInt& b) { return a.x >= b.x; }
	static ModInt sign(long long k) { return ((k & 1) ? ModInt(MOD-1) : ModInt(1)); }


	ModInt& operator += (const ModInt& m) { x += m.x; if(x >= MOD) x -= MOD; return *this; }
	ModInt& operator -= (const ModInt& m) { x -= m.x; if(x < 0LL) x += MOD; return *this; }
	ModInt& operator *= (const ModInt& m) { x = (1LL * x * m.x) % MOD; return *this; }

	friend ModInt operator - (const ModInt& a) { ModInt res(a); if(res.x) res.x = MOD - res.x; return res; }
	friend ModInt operator + (const ModInt& a, const ModInt& b) { return ModInt(a) += ModInt(b); }
	friend ModInt operator - (const ModInt& a, const ModInt& b) { return ModInt(a) -= ModInt(b); }
	friend ModInt operator * (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b); }

	static long long fp(long long u, long long k) {
		long long res = 1LL;
		while(k > 0LL) {
			if(k & 1LL) res = (res * u) % MOD;
			u = (u * u) % MOD;
			k /= 2LL;
		}
		return res;
	}

	static constexpr int mod() {return MOD;}

	ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
	ModInt inv() { return ModInt(fp(x, MOD-2)); }
	ModInt& operator /= (const ModInt& m) { return *this *= ModInt(m).inv(); }
	friend ModInt operator / (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b).inv(); }

	friend ostream& operator << (ostream& out, const ModInt& a) { return out << a.x; }
	friend istream& operator >> (istream& in, ModInt& a) {return in >> a.x;}
};

const int MOD = 1e9 + 9;
using Mint = ModInt<MOD>;

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n, inputSeq))
		return 0;
	int posValid(0);
	while (posValid < n and inputSeq[posValid] > n)
		posValid++;
	
	Mint sol(1);
	vector<int> toReplace;
	for (int i(0); i < n; ++i)
		if (inputSeq[i] > n)
			toReplace.push_back(inputSeq[i] - n);
	sort(toReplace.begin(), toReplace.end());
	int prv(0);
	for (int i(0); i < (int)toReplace.size(); ++i)
	{
		sol *= Mint(toReplace.size() - i).fastpow(toReplace[i] - prv-1);
		prv = toReplace[i];
	}
	if (posValid == n)
		sol *= n;

  return sol.x;
}

• 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