Submission #393863

#	Time	Username	Problem	Language	Result	Execution time	Memory
393863		rainboy	Jousting tournament (IOI12_tournament)	C11	49 / 100	1087 ms	1680 KiB

tournament

#include <stdio.h>
#define N	100000

int GetBestPosition(int n, int m, int r, int *aa, int *ll, int *rr) {
	static int ii[N + 1], rr_[N];
	int h, i, n_, n1, i_, k_, k;

	for (i = 0; i <= n; i++)
		ii[i] = i;
	n_ = n + 1;
	for (h = 0; h < m; h++) {
		ll[h] = ii[ll[h]], rr[h] = ii[rr[h] + 1] - 1;
		n1 = 0;
		for (i = 0; i < n_; i++)
			if (ii[i] <= ll[h] || ii[i] > rr[h])
				ii[n1++] = ii[i];
		n_ = n1;
	}
	rr_[n - 1] = n - 1;
	for (i = n - 2; i >= 0; i--)
		rr_[i] = aa[i] > r ? i : rr_[i + 1];
	i_ = -1, k_ = -1;
	for (i = 0; i < n; i++) {
		k = 0;
		for (h = 0; h < m; h++)
			if (ll[h] <= i && i <= rr[h]) {
				if (rr_[ll[h]] < rr[h])
					break;
				k++;
			}
		if (k_ < k)
			k_ = k, i_ = i;
	}
  return i_;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51