Submission #1163971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163971		an22inkle	Gondola (IOI14_gondola)	C++20	55 / 100	32 ms	4680 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

int valid(int n, int v[]) {

	map<int, bool> freq;
	int mi = -1;
	for (int i = 0; i < n; i++) {
		if (freq[v[i]]) return 0;

		freq[v[i]] = 1;
		if (v[i] <= n && (mi == -1 || v[i] < v[mi])) {
			mi = i;
		}
	}



	if (mi == -1) {
		return 1;
	}

	int prevj = mi;
	for (int j = mi + 1; j <= (n + mi - 1); j++) {
		int i = j % n;
		if (v[i] > n) continue;
		// cout << prevj << ' ' << j << '\n';
		// cout <<  v[prevj % n] << ' ' << (v[i]) << '\n';
		// cout <<  abs(j - prevj) << ' ' << abs(v[i] - v[prevj  % n]) << '\n';
		// cout << '\n';
		if (v[i] < v[prevj % n] or abs(j - prevj) != abs(v[i] - v[prevj % n])) return 0;
		prevj = j;
	}

	return 1;

}

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

int replacement(int n, int v[], int ans[]) {
	int LASTI = -1;
	function<void(int)> pb = [&](int a) {
		LASTI++;
		ans[LASTI] = a;
  	};


  	int mi = -1;
  	for (int i = 0; i < n; i++) {
		if (v[i] <= n && (mi == -1 || v[i] < v[mi])) {
			mi = i;
		}
	}

	vector<int> original(n);
	if (mi == -1) {
		iota(original.begin(), original.end(), 1);
	} else {
		int set = v[mi];
		for (int i = 1; set - i > 0; i++) {
			int j = (mi - i);
			if (j < 0) j = n + j;
			original[j] = set - i;
		}

		for (int i = 1; set + i <= n; i++) {
			int j = (mi + i) % n;
			original[j] = set + i;
		}
	}

	original[mi] = v[mi];

  	vector<pair<int, int>> ord;
  	for (int i = 0; i < n; i++) {
  		if (v[i] > n) ord.push_back({v[i], original[i]});
  	}
  	sort(ord.begin(), ord.end());

  	int count = 0;
  	int last = n + 1;
  	for (int i = 0; i < ord.size(); i++) {
  		// cout << last << ' ' << ord[i].first << '\n';
  		int run = 0;
  		while (last != ord[i].first + 1) {
  			if (run == 0) {
  				pb(ord[i].second);
  			} else {
  				pb(last - 1);
  			}
  			count++, last++, run++;
  		}
  	}

  	return count;
}

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

int countReplacement(int n, int inputSeq[])
{
  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