Submission #779686

#	Time	Username	Problem	Language	Result	Execution time	Memory
779686		I_Love_EliskaM_	The Big Prize (IOI17_prize)	C++14	90 / 100	406 ms	5404 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {return a+rng()%(b-a+1);}

map<int,vector<int>> mem;
vector<int> query(int i) {
	if (mem.count(i)) return mem[i];
	mem[i]=ask(i);
	return mem[i];
}

struct BIT {
	vector<int> t; int n;
	BIT(int n) {
		this->n = n;
		t.assign(n,0);
	}
	void add(int i, int x) {
		for(;i<n;i=i|(i+1)) t[i]+=x;
	}
	int sum(int r) {
		int q=0; for(;r>=0;r=(r&(r+1))-1) q+=t[r]; return q;
	}
};

int find_best(int n) {
	BIT ft(n);
	int f=0,s=0;
	map<int,int> was;
	vector<pi> z;
	forn(it,min(473,n)) {
		int i=rng()%n;
		if (was[i]) {
			--it; continue;
		}
		was[i]=1;
		auto q = query(i);
		z.pb({i,q[0]+q[1]});
		if (q[0]+q[1]==0) return i;
		if (q[0]+q[1]>f) {
			f=q[0]+q[1], s=i;
		}
	}
	vector<int> ok(n);
	for(auto&x:z) if (x.s!=f) {ok[x.f]=1; ft.add(x.f,1);}
	
	vector<int> p; forn(i,n) if (!ok[i]) p.pb(i);
	forn(it,f) {
		n=p.size();
		int l=0, r=n-1;
		while (l<r) {
			int m=(l+r)>>1;
			int x=p[m];
			auto q=query(x);
			if (q[0]+q[1]==0) return x;
			if (q[0]+q[1]!=f) {
				vector<int> b; forn(i,n) if (i!=m) b.pb(p[i]);
				p=b;
				ft.add(x,1);
				break;
			}
			if (q[0]==ft.sum(x)) l=m+1;
			else r=m;
		}
		if (p.size()<n) continue;
		int x=p[r];
		auto q=query(x);
		if (q[0]+q[1]==0) return x;
		vector<int> b; forn(i,n) if (i!=r) b.pb(p[i]);
		p=b;
		ft.add(x,1);
		if (!p.size()) break;
	}
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:72:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   if (p.size()<n) continue;
      |       ~~~~~~~~^~
prize.cpp:8:11: warning: variable 'second' set but not used [-Wunused-but-set-variable]
    8 | #define s second
      |           ^~~~~~
prize.cpp:35:10: note: in expansion of macro 's'
   35 |  int f=0,s=0;
      |          ^

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