Submission #779809

#	Time	Username	Problem	Language	Result	Execution time	Memory
779809		I_Love_EliskaM_	The Big Prize (IOI17_prize)	C++14	100 / 100	168 ms	2432 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=-1;
	map<int,int> was;
	vector<pi> z;
	
	const int T=1<<8;
	vector<int> p; forn(i,n) p.pb(i);
	
	vector<int> t;

	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) 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]>f) {
				f=q[0]+q[1];
				for(auto&x:t) ft.add(x,1);
				t.clear();
			}
			if (q[0]+q[1]==0) return x;
			if (q[0]+q[1]<f) {
				ft.add(x,1);
				z.pop_back();
				continue;
			} 
			t.pb(x);
			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) {
					f=q[0]+q[1];
					for(auto&x:t) ft.add(x,1);
					t.clear();
				}
				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;
				t.pb(x);
			}
			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:94:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |    if (z.size()<k) continue;
      |        ~~~~~~~~^~
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:51:7: note: 'Z' was declared here
   51 |   int Z;
      |       ^

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