oj.uz

Submission #371269

# Submission time Handle Problem Language Result Execution time Memory
371269 2021-02-26T10:19:17 Z peijar Gondola (IOI14_gondola) C++17
100 / 100
 221 ms 6124 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 20 ms 2284 KB Output is correct
7 Correct 11 ms 748 KB Output is correct
8 Correct 32 ms 3948 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 36 ms 4588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 16 ms 2284 KB Output is correct
7 Correct 11 ms 748 KB Output is correct
8 Correct 31 ms 3948 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 35 ms 4588 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 20 ms 2156 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 48 ms 4716 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 181 ms 4460 KB Output is correct
12 Correct 40 ms 4972 KB Output is correct
13 Correct 29 ms 2796 KB Output is correct
14 Correct 221 ms 4468 KB Output is correct
15 Correct 30 ms 2940 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 47 ms 4588 KB Output is correct
10 Correct 38 ms 3820 KB Output is correct
11 Correct 14 ms 1644 KB Output is correct
12 Correct 17 ms 1900 KB Output is correct
13 Correct 4 ms 748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 50 ms 4588 KB Output is correct
10 Correct 41 ms 3948 KB Output is correct
11 Correct 14 ms 1644 KB Output is correct
12 Correct 17 ms 1900 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 63 ms 5484 KB Output is correct
15 Correct 89 ms 6124 KB Output is correct
16 Correct 11 ms 1388 KB Output is correct
17 Correct 45 ms 4204 KB Output is correct
18 Correct 23 ms 2540 KB Output is correct