Submission #1164041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164041		an22inkle	Gondola (IOI14_gondola)	C++20	75 / 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 v[]) {
	long long MOD =  1e9 + 9;
  function<long long(int, int)> pow = [&](int a, int n) {
  	if (a == 0) return 0LL;
  	if (n == 0) return 1LL;
  	if (n == 1) {
  		return 1LL*a;
  	}

  	long long half = 1LL*pow(a, n/2) % MOD ;
  	long long res = (half*half) % MOD;

  	if (n % 2 == 1) {
  		return res*1LL*a % MOD;
  	}

  	return res;
  };

  if (!valid(n, v)) {
  	return 0;
  }

  vector<int> res;
  for (int i = 0; i < n; i++) {
  	if (v[i] > n) res.push_back(v[i] - n);
  }

  if (res.size() == 0) {
  	return 1;
  }

  sort(res.begin(), res.end());
  
  long long ans = pow((int)res.size(), res[0] - 1);
  for (int i = 1; i < res.size(); i++) {
  	long long r = pow((int)res.size() - i, res[i] - res[i - 1] - 1);
  	// cout << r << '\n';
  	ans *= (r%MOD);
  	ans %= MOD;
  }

  return (int)ans;
}

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