Submission #779679

#	Time	Username	Problem	Language	Result	Execution time	Memory
779679		I_Love_EliskaM_	The Big Prize (IOI17_prize)	C++14	90 / 100	355 ms	4704 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
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) {
	//cout<<"! q "<<i<<'\n';
	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;
	}
};

const int test=0;
int find_best(int n) {
	BIT ft(n);
	int f=0,s=0;
	if (test) {
		cin>>f;
	} else {
		forn(it,1000) {
			int i=rng()%n;
			auto q = query(i);
			if (q[0]+q[1]==0) return i;
			if (q[0]+q[1]>f) {
				f=q[0]+q[1], s=i;
			}
		}
	}
	
	vector<int> p(n); forn(i,n) p[i]=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:66:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if (p.size()<n) continue;
      |       ~~~~~~~~^~
prize.cpp:34:10: warning: variable 's' set but not used [-Wunused-but-set-variable]
   34 |  int f=0,s=0;
      |          ^

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