Submission #593051

#	Time	Username	Problem	Language	Result	Execution time	Memory
593051		Tekor	The Big Prize (IOI17_prize)	C++17	90 / 100	65 ms	9792 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N],gd[N];
vector <pii> q; 
int t[N * 4],t1[N * 4];
void build(int v,int tl,int tr) {
	if(tl == tr) {
		t[v] = 1;
		t1[v] = 0;
		return;
	}
	int tm = (tl + tr) / 2;
	build(v + v,tl,tm);
	build(v + v + 1,tm + 1,tr);
	t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int x) {
	if(tl == tr)return tl;
	int tm = (tl + tr) / 2;
	if(t[v + v] >= x)return get(v + v,tl,tm,x);
	else return get(v + v + 1,tm + 1,tr,x - t[v + v]);
}
void upd(int v,int tl,int tr,int pos) {
	if(tl == tr) {
		t[v] = 0;
		t1[v] = 1;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos);
	else upd(v + v + 1,tm + 1,tr,pos);
	t[v] = t[v + v] + t[v + v + 1];
	t1[v] = t1[v + v] + t1[v + v + 1];
}
int get1(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t1[v];
	int tm = (tl + tr) / 2;
	return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
	if(u[x])return was[x];
	u[x] = 1;
	kol++;
	assert(kol <= 10000);
	was[x] = ask(x);
	return was[x];
}
int find_best(int pp) {
	k = pp;
	int m = (k - 1) / 2;
	int mx = 1;
	build(1,0,k - 1);
	int pos = 0;
	while(1) {
		int l = 0,r = k - 1 - pos;
		while(l <= r) {
			int mid = (l + r) / 2;
			int zap = get(1,0,k - 1,mid + 1);
			vector <int> res = Ask(zap);
			int sum = res[0] + res[1];
			if(sum == 0)return zap;
			if(sum < mx) {
				pos++;
				upd(1,0,k - 1,zap);
				gd[zap] = 1;
				break;
			}
			if(sum > mx) {
				bool ch = 0;
				for(int i = 0;i < k;i++) {
					if(!gd[i] && u[i] && i != zap) {
						pos++;
						upd(1,0,k - 1,i);
						ch = 1;
						gd[i] = 1;
					}
				}
				mx = sum;
				if(ch)break;
			}
			res[0] -= get1(1,0,k - 1,0,zap - 1);
			if(res[0] != 0) {
				r = mid - 1;
			}else {
				l = mid + 1;
			}
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:6: warning: unused variable 'm' [-Wunused-variable]
   66 |  int m = (k - 1) / 2;
      |      ^

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