Submission #779696

#	Time	Username	Problem	Language	Result	Execution time	Memory
779696		I_Love_EliskaM_	The Big Prize (IOI17_prize)	C++14	20 / 100	88 ms	3112 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);}
	
	vector<int> p; forn(i,n) if (!ok[i]) p.pb(i);
	for (int l=0; l<n; l+=512) {
		int r=l+511; r=min(r,n-1);
		vector<int> z;
		for(auto&x:p) if (!ok[x]) if (l<=x && x<=r) z.pb(x);
		int k=z.size();
		int R=0;
		for (int j=l+512; j<n; ++j) {
			auto q=query(j);
			if (q[0]+q[1]==0) return j;
			if (q[0]+q[1]!=f) {
				if (!ok[j]) ft.add(j,1);
				ok[j]=1; continue;
			}
			R=q[1]; break;
		}
		auto q=query(l);
		if (q[0]+q[1]==0) return l;
		int Z=q[1]-R-(ft.sum(n-1)-ft.sum(r));
		//cout<<"! "<<l<<' '<<r<<' '<<k<<' '<<Z<<' '<<R<<'\n';
		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;
					if (!ok[x]) ft.add(x,1);
					ok[x]=1;
					break;
				}
				if (q[0]==ft.sum(x)) lq=m+1;
				else rq=m;
			}
			if (z.size()<k) continue;
			int x=z[r];
			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;
			if (!ok[x]) ft.add(x,1);
			ok[x]=1;
			if (!z.size()) break;
		}
	}
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:95:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |    if (z.size()<k) continue;
      |        ~~~~~~~~^~
prize.cpp:61:7: warning: unused variable 'k' [-Wunused-variable]
   61 |   int k=z.size();
      |       ^
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;
      |          ^

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