Submission #779798

#	Time	Username	Problem	Language	Result	Execution time	Memory
779798		I_Love_EliskaM_	The Big Prize (IOI17_prize)	C++14	99.70 / 100	172 ms	3164 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);}
#define all(x) x.begin(),x.end()

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);}
	
	const int T=1<<8;
	vector<int> p; forn(i,n) p.pb(i);

	vector<int> zzz;
	for (int l=0; l<n; l+=T) {
		int r=l+T-1; r=min(r,n-1);
		vector<int> z;
		for(auto&x:p) if (l<=x && x<=r) if (!ok[x]) z.pb(x);

		int Z;
		int k=z.size();
		for (int j=k-1; j>=0; --j) {
			int x=z[j];
			auto q=query(x);
			if (q[0]+q[1]==0) return x;
			if (q[0]+q[1]!=f) {
				ft.add(x,1);
				z.pop_back();
				continue;
			}
			Z=q[0]-ft.sum(r); break;
		}
		forn(it,Z) {
			int k=z.size();
			int r=k-1;
			int lq=0, rq=r;
			while (lq<rq) {
				int m=(lq+rq)>>1;
				int x=z[m];
				auto q=query(x);
				if (q[0]+q[1]==0) return x;
				if (q[0]+q[1]!=f) {
					vector<int> b; forn(i,k) if (i!=m) b.pb(z[i]);
					z=b;
					ft.add(x,1);
					break;
				}
				if (q[0]==ft.sum(x)) lq=m+1;
				else rq=m;
			}
			if (z.size()<k) continue;
			int x=z[r];
			if (!mem.count(x)) zzz.pb(x);
			else {
				auto q=query(x);
				if (q[0]+q[1]==0) return x;
			}
			vector<int> b; forn(i,k) if (i!=r) b.pb(z[i]);
			z=b;
			ft.add(x,1);
			if (!z.size()) break;
		}
	}
	shuffle(all(zzz),rng);
	for(auto&x:zzz) {
		auto q=query(x); if (q[0]+q[1]==0) return x;
	}
} 

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:96:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |    if (z.size()<k) continue;
      |        ~~~~~~~~^~
prize.cpp:8:11: warning: variable 'second' set but not used [-Wunused-but-set-variable]
    8 | #define s second
      |           ^~~~~~
prize.cpp:36:10: note: in expansion of macro 's'
   36 |  int f=0,s=0;
      |          ^
prize.cpp:35:10: warning: control reaches end of non-void function [-Wreturn-type]
   35 |  BIT ft(n);
      |          ^
prize.cpp:4:32: warning: 'Z' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
      |                                ^
prize.cpp:65:7: note: 'Z' was declared here
   65 |   int Z;
      |       ^

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