Submission #1320275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320275		orgiloogii	Gondola (IOI14_gondola)	C++20	25 / 100	32 ms	4788 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;
	if (idx == -1) {
	    sz = n;
	    for (int i = 0;i < n;i++) {
	        r[i] = i + 1;
	    }
	}
	else {
	    vector <pair <int, int>> v;
	    for (int i = 0;i < n;i++) {
	        if (g[i] != exp[i]) {
	            v.push_back({g[i], exp[i]});
	        }
	    }
	    sort(v.begin(), v.end());
	    for (int i = 0;i < v.size();i++) {
	        r[sz] = v[i].second;
	        sz++;
	    }
	}
    for (int i = n + 1;i <= mx;i++) {
        if (vis[i] == false) {
            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: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10