Submission #2193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2193	2013-07-20T09:09:13 Z	kriii	Jousting tournament (IOI12_tournament)	C++	100 / 100	46 ms	4616 KB

tournament

const int Z = 1 << 17;
int next[Z],cnt[Z*2];

int getnth(int n)
{
	int x = 1;

	while (x < Z){
		x <<= 1;
		if (cnt[x] < n) n -= cnt[x++];
	}

	return x - Z;
}

void up(int x, int p)
{
	x += Z;
	while (x){
		cnt[x] += p;
		x >>= 1;
	}
}

int add[Z],res[Z];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int i,peo,x,y;

	for (i=0;i<N;i++) next[i] = i+1, cnt[i+Z] = 1;
	for (i=Z-1;i>=1;i--) cnt[i] = cnt[i*2] + cnt[i*2+1];
	
	for (i=0;i<C;i++){
		peo = E[i] - S[i];
		S[i] = getnth(S[i]+1);
		x = next[S[i]];
		while (peo--){
			up(x,-1);
			x = next[x];
		}
		E[i] = x - 1;
		next[S[i]] = x;
	}

	for (i=1;i<N;i++) add[i] = add[i-1] + (K[i-1] > R);

	for (i=0;i<C;i++){
		if (add[E[i]] == add[S[i]]){
			res[S[i]]++;
			res[E[i]]--;
		}
	}

	int s = 0, p = -1, ind;
	for (i=0;i<N;i++){
		s += res[i];
		if (p < s){
			p = s;
			ind = i;
		}
	}

	return ind;
}

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3472 KB	Output is correct
2	Correct	0 ms	3472 KB	Output is correct
3	Correct	0 ms	3472 KB	Output is correct
4	Correct	0 ms	3472 KB	Output is correct
5	Correct	0 ms	3472 KB	Output is correct
6	Correct	0 ms	3472 KB	Output is correct
7	Correct	0 ms	3472 KB	Output is correct
8	Correct	0 ms	3472 KB	Output is correct
9	Correct	0 ms	3472 KB	Output is correct
10	Correct	0 ms	3472 KB	Output is correct

Subtask #2

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3472 KB	Output is correct
2	Correct	1 ms	3472 KB	Output is correct
3	Correct	0 ms	3472 KB	Output is correct
4	Correct	2 ms	3472 KB	Output is correct
5	Correct	1 ms	3472 KB	Output is correct
6	Correct	2 ms	3472 KB	Output is correct
7	Correct	2 ms	3472 KB	Output is correct
8	Correct	1 ms	3472 KB	Output is correct
9	Correct	0 ms	3472 KB	Output is correct
10	Correct	2 ms	3472 KB	Output is correct

Subtask #3

51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3916 KB	Output is correct
2	Correct	43 ms	4616 KB	Output is correct
3	Correct	19 ms	3864 KB	Output is correct
4	Correct	45 ms	4616 KB	Output is correct
5	Correct	39 ms	4580 KB	Output is correct
6	Correct	35 ms	4352 KB	Output is correct
7	Correct	41 ms	4616 KB	Output is correct
8	Correct	46 ms	4616 KB	Output is correct
9	Correct	15 ms	3864 KB	Output is correct
10	Correct	19 ms	3864 KB	Output is correct