Submission #114378

#	Time	Username	Problem	Language	Result	Execution time	Memory
114378		E869120	Gondola (IOI14_gondola)	C++14	100 / 100	98 ms	6044 KiB

gondola

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

int valid(int n, int inputSeq[]) {
	int minx = (1 << 30), minid = -1; map<int, int>Map;
	for (int i = 0; i < n; i++) { if (minx > inputSeq[i]) { minx = inputSeq[i]; minid = i; } if (Map[inputSeq[i]] == 1) return 0; Map[inputSeq[i]] = 1;}
	for (int i = 0; i < n; i++) {
		int s = (i + minid) % n;
		if (inputSeq[s] <= n && inputSeq[s] != i + minx) return 0;
	}
	return 1;
}

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

int id[250009];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int G = 0; for (int i = 0; i < n; i++) { if (gondolaSeq[i] <= n) G = (i - (gondolaSeq[i] - 1) + n) % n; }
	
	int maxn = 0;
	for (int i = 0; i <= 250000; i++) id[i] = -1;
	for (int i = 0; i < n; i++) { id[gondolaSeq[i]] = (i - G + n) % n; maxn = max(maxn, gondolaSeq[i]); }
	
	for (int i = 0; i < n; i++) gondolaSeq[i] = i + 1;
	for (int i = n + 1; i <= maxn; i++) {
		if (id[i] >= 0) {
			replacementSeq[i - (n + 1)] = gondolaSeq[id[i]];
			gondolaSeq[id[i]] = i;
		}
		else {
			replacementSeq[i - (n + 1)] = gondolaSeq[id[maxn]];
			gondolaSeq[id[maxn]] = i;
		}
	}
	return maxn - n;
}

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

const int mod = 1000000009;

long long modpow(int a, int b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 31; i++) {
		if ((b / (1 << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

int countReplacement(int n, int inputSeq[]) {
	if (valid(n, inputSeq) == 0) return 0;
	
	vector<int>vec; vec.push_back(n);
	for (int i = 0; i < n; i++) { if (inputSeq[i] > n) vec.push_back(inputSeq[i]); }
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	
	long long F = 1;
	for (int i = 0; i < vec.size() - 1; i++) {
		long long E = modpow(i + 1, vec[i] - vec[i + 1] - 1, mod);
		F *= E; F %= mod;
	}
	if ((int)vec.size() > n) { F *= n; F %= mod; }
	return (int)F;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~~

• 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: 15 / 15
• Subtask 10: 10 / 10