Submission #790225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790225	2023-07-22T12:36:46 Z	Sohsoh84	Gondola (IOI14_gondola)	C++17	100 / 100	78 ms	11496 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define all(x)		(x).begin(), (x).end()

const int MAXN = 1e6 + 10;

typedef long long ll;
typedef pair<ll, ll> pll;

int A[MAXN];

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

int replacement(int n, int inputSeq[], int res[]) {
	for (int i = 0; i < n; i++) inputSeq[i]--;
	
	int s = -1;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] < n)
			s = i;
	}

	int shift_val = (s == -1 ? 0 : (s - inputSeq[s] + n) % n);
	for (int j = 0; j < n; j++)
		A[j] = inputSeq[(j + shift_val) % n];

	set<int> st;
	int mx = *max_element(A, A + n);
	for (int i = 0; i <= mx; i++)
		st.insert(i);

	for (int i = 0; i < n; i++)
		st.erase(A[i]);

	set<pll> gond;
	for (int i = 0; i < n; i++)
		gond.insert({A[i], i});

	int m = 0;
	while (gond.rbegin() -> X >= n) {
		auto [x, ind] = *prev(gond.end());
		gond.erase(prev(gond.end()));
		if (st.find(x - 1) != st.end()) {
			A[ind] = x - 1;
			st.erase(x - 1);
			res[m++] = x - 1;
		} else {
			A[ind] = ind;
			st.erase(ind);
			res[m++] = ind;
		}

		gond.insert({A[ind], ind});
	}

	reverse(res, res + m);
	for (int i = 0; i < m; i++)
		res[i]++;
	return m;
}

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

const ll MOD = 1e9 + 9;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}

	return ans;
}

int valid(int n, int inputSeq[]) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	set<int> st;
	for (int i = 0; i < n; i++) {
		if (st.count(inputSeq[i])) return 0;
		st.insert(inputSeq[i]);
	}
	int lowest = 1e9, pos = 1e9;
	for (int i = 0; i < n; i++) {
		if (lowest > inputSeq[i]) {
		   	lowest = inputSeq[i], pos = i;
		}
	}
	if (lowest > n) return 1;
	for (int i = pos, cnt = lowest, len = 1; len <= n; i = (i + 1) % n, len++, cnt = cnt % n + 1) {
		if (inputSeq[i] > n) continue;
		if (cnt != inputSeq[i]) return 0;
	}
	return 1;
}
 

int countReplacement(int n, int inputSeq[]) {
	if (!valid(n, inputSeq)) return 0;
	ll ans = n;
	vector<ll> vec;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] > n) vec.push_back(inputSeq[i]);
		else ans = 1;
	}

	sort(all(vec));
	ll x = n + 1;
	for (int i = 0; i < int(vec.size()); i++) {
		ans = ans * poww(int(vec.size()) - i, vec[i] - x) % MOD;
		x = vec[i] + 1;
	}

	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	10 ms	2132 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	20 ms	3956 KB	Output is correct
9	Correct	6 ms	1492 KB	Output is correct
10	Correct	24 ms	4528 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	11 ms	2260 KB	Output is correct
7	Correct	6 ms	596 KB	Output is correct
8	Correct	19 ms	3916 KB	Output is correct
9	Correct	6 ms	1492 KB	Output is correct
10	Correct	24 ms	4428 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	13 ms	2004 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	30 ms	4608 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	31 ms	5784 KB	Output is correct
12	Correct	35 ms	6576 KB	Output is correct
13	Correct	59 ms	7532 KB	Output is correct
14	Correct	31 ms	5688 KB	Output is correct
15	Correct	78 ms	11496 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	31 ms	4448 KB	Output is correct
10	Correct	25 ms	3788 KB	Output is correct
11	Correct	9 ms	1508 KB	Output is correct
12	Correct	11 ms	1852 KB	Output is correct
13	Correct	3 ms	596 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	308 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	32 ms	4512 KB	Output is correct
10	Correct	25 ms	3772 KB	Output is correct
11	Correct	9 ms	1604 KB	Output is correct
12	Correct	11 ms	1900 KB	Output is correct
13	Correct	3 ms	724 KB	Output is correct
14	Correct	37 ms	5324 KB	Output is correct
15	Correct	43 ms	5984 KB	Output is correct
16	Correct	7 ms	1396 KB	Output is correct
17	Correct	28 ms	4104 KB	Output is correct
18	Correct	15 ms	2764 KB	Output is correct

Submission #790225

Compilation message