Submission #114375

#	Time	Username	Problem	Language	Result	Execution time	Memory
114375		E869120	Gondola (IOI14_gondola)	C++14	55 / 100	52 ms	4728 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 + 1) 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;
}

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

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