Submission #248795

#	Time	Username	Problem	Language	Result	Execution time	Memory
248795		kostia244	The Big Prize (IOI17_prize)	C++17	20 / 100	93 ms	2036 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using vi = vector<int>;
int solve(vector<int> p) {
	if(p.size() < 100) {
	for(auto i : p) {
		std::vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
	}
	while(true);
	}
	int cb = 1<<30, cg;
	vi g, pg;
	for(int i = 0; i < 36; i++) {
		vi t = ask(p[i]);
		cb = min(cb, (int)p.size() - t[0] - t[1]);
	}
	cg = p.size() - cb;
	//cout << cg << " "  << cb << endl;
	for(int j = -1, i = 0; i < cg;) {
		for(int z = 1<<18; z>>=1;) {
			int nj = j+z;
			while(nj < p.size()) {
				if(count(all(g), p[nj]) || count(all(pg), p[nj])) {
					nj++;
					continue;
				}
				vi t = ask(p[nj]);
				if(t[0]+t[1] < cg) pg.push_back(p[nj++]);
				else break;
			}
			if(nj >= p.size()) continue;
			//cout << j << " // " << nj << " " << ask(p[nj])[0] << endl;
			if(ask(p[nj])[0] <= i) j = nj;
		}
		int nj = j+1;
		while(nj < p.size()) {
			if(count(all(g), p[nj])) {
				nj++;
				continue;
			}
			vi t = ask(p[nj]);
			if(t[0]+t[1] < cg) g.push_back(p[nj++]);
			else break;
		}
		i = g.size();
		j = min((int)p.size()-1, nj);
		//if(j != 1999)
		//cout << j << " " << i << " " << g.size() << " " << cg << " " << (nj<p.size()?ask(p[nj])[0]:-1) << endl;
	}
	return solve(g);
}
int find_best(int n) {
	vi t;
	for(int i = 0; i < n; i++) t.push_back(i);
	return solve(t);
}

Compilation message (stderr)

prize.cpp: In function 'int solve(std::vector<int>)':
prize.cpp:26:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(nj < p.size()) {
          ~~~^~~~~~~~~~
prize.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nj >= p.size()) continue;
       ~~~^~~~~~~~~~~
prize.cpp:40:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(nj < p.size()) {
         ~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80