Submission #1297450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297450		Jawad_Akbar_JJ	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	404 KiB

prize

#include <iostream>
#include <vector>
#include "prize.h"

using namespace std;
int tot, Ans = -1, Q, lst = -1;
vector<int> res;

// vector<int> Ask(int id){
// 	return {};
// }

vector<int> Ask(int id){
	Q++;
	if (Q > 10000)
		cout<<1 / 0;
	return ask(id);
}

void Solve(int l, int r, int k, int cnt){
	vector<int> rs;
	if (cnt == 0 or l == r 	or Ans != -1)
		return;
	// cout<<l<<" "<<r<<" "<<cnt<<endl;

	int mid = (l + r) / 2;
	rs = Ask(mid);
	// cout<<l<<" "<<mid<<" "<<r<<" "<<k<<" "<<cnt<<" "<<rs[0]<<" "<<rs[1]<<endl;

	if (rs[0] + rs[1] != tot){
		int m1 = mid + 1;
		if (rs[0] + rs[1] == 0)
			Ans = mid;
		while (m1 < r and Ans == -1){
			rs = Ask(m1);
			if (rs[0] + rs[1] == 0)
				Ans = m1;
			if (rs[0] + rs[1] == tot)
				break;
			m1++;
		}

		// cout<<"here "<<m1<<" "<<rs[0]<<" "<<rs[1]<<endl;

		if (rand() % 2){
			if (m1 == r)
				Solve(l, mid, k, cnt - (m1 - mid));
			else
				Solve(l, mid, k, k - rs[1] - (m1 - mid));
			
			
			Solve(m1, r, rs[1], cnt - (k - rs[1]));
		}
		else{
			Solve(m1, r, rs[1], cnt - (k - rs[1]));

			if (m1 == r)
				Solve(l, mid, k, cnt - (m1 - mid));
			else
				Solve(l, mid, k, k - rs[1] - (m1 - mid));
			
		}
		return;
	}

	if (rand() % 2){
		Solve(l, mid, k, k - rs[1]);
		Solve(mid+1, r, rs[1], cnt - (k - rs[1]));
	}
	else{
		Solve(mid+1, r, rs[1], cnt - (k - rs[1]));
		Solve(l, mid, k, k - rs[1]);
	}	
}

int find_best(int n){
	srand(time(0));

	for (int i=1;i<=20;i++){
		int id = rand() % n;
		res = Ask(id);
		tot = max(tot, res[0] + res[1]);
	}

	Solve(0, n, tot, tot);
	return Ans;
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<int> Ask(int)':
prize.cpp:16:25: warning: division by zero [-Wdiv-by-zero]
   16 |                 cout<<1 / 0;
      |                       ~~^~~

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