Submission #1320301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320301		orgiloogii	Gondola (IOI14_gondola)	C++20	55 / 100	32 ms	5212 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int g[]) {
	int idx = -1;
	map <int, bool> vis;
	for (int i = 0;i < n;i++) {
		if (vis[g[i]] == true) return 0;
		vis[g[i]] = true;
		if (g[i] <= n && idx == -1) {
			idx = i;
		}
	}
	if (idx == -1) return 1;
	int cnt = g[idx];
	for (int i = idx + 1;;i++) {
		i %= n;
		if (i == idx) break;
		cnt %= n;
		cnt++;
		if (g[i] <= n && g[i] != cnt) return 0;
	}
	return 1;
}

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

int replacement(int n, int g[], int r[]) {
    int idx = -1;
	map <int, bool> vis;
	int mx = 0;
	for (int i = 0;i < n;i++) {
		if (vis[g[i]] == true) return 0;
		vis[g[i]] = true;
		if (g[i] <= n && idx == -1) {
			idx = i;
		}
		mx = max(mx, g[i]);
	}
	int sz = 0;
	int exp[n] = {0};
	if (idx == -1) {
		exp[0] = 1;
		int cnt = 1;
		for (int i = 1;;i++) {
			i %= n;
			if (i == 0) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	else {
		exp[idx] = g[idx];
		int cnt = g[idx];
		for (int i = idx + 1;;i++) {
			i %= n;
			if (i == idx) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	// for (int i = 0;i < n;i++) {
	// 	cout << exp[i] << ' ';
	// }
	// cout << endl;
	vector <pair <int, int>> upd;
	for (int i = 0;i < n;i++) {
		if (exp[i] != g[i]) {
			upd.push_back({g[i], exp[i]});
		}
	}
	sort(upd.begin(), upd.end());
	for (auto [x, y] : upd) {
		r[sz] = y;
		sz++;
		for (int i = n + sz;i < x;i++) {
			r[sz] = i;
			sz++;
		}
	}
	return mx - n;
}


int countReplacement(int n, int g[]) {
  return -3;
}

• 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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10