oj.uz

Submission #139954

# Submission time Handle Problem Language Result Execution time Memory
139954 2019-08-01T17:45:34 Z arthurconmy The Big Prize (IOI17_prize) C++14
20 / 100
 109 ms 1996 KB 
#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "prize.h"
#endif

using namespace std;

// NB: ask(i) returns a two-elem vector<int>

const int MAXN=200000;

bool asked[MAXN];
pair<int,int> answers[MAXN];

#ifdef ARTHUR_LOCAL
	vector<int> real_deal;

	vector<int> ask(int n)
	{
		int ans1=0;
		int ans2=0;

		for(int i=0; i<n; i++)
		{
			if(real_deal[i]<real_deal[n]) ans1++;
		}

		for(int i=n; i<8; i++)
		{
			if(real_deal[i]<real_deal[n]) ans2++;
		}

		return {ans1,ans2};
	}
#endif

pair<int,int> get_ans(int n)
{	
	//cout << n << endl;

	if(asked[n]) return answers[n];

	vector<int> cur = ask(n);
	answers[n] = {cur[0],cur[1]};
	return answers[n];
}	

int find_best(int n) 
{
	// query 30 random places in order to determine the minimum thing

	random_device rd;  
    mt19937 gen(rd()); 
    uniform_int_distribution<> dis(1,1000000000);

	int max_side=0;

	for(int i=0; i<100; i++)
	{
		pair<int,int> cur = get_ans(dis(gen)%n);
		max_side = max(max_side,cur.first+cur.second);
	}

	int left = 0;
	int right = n-1;

	while(true)
	{
		pair<int,int> cur = get_ans(left);

		if(cur.first + cur.second == 0) return left;
		if(cur.first + cur.second == max_side) break;

		left++;
	}

	while(true)
	{
		pair<int,int> cur = get_ans(right);

		if(cur.first + cur.second == 0) return right;
		if(cur.first + cur.second == max_side) break;

		right--;
	}

	//cout << left << " " << right << endl;

	vector<pair<int,int>> I = {make_pair(left,right)};

	while(true)
	{
		vector<pair<int,int>> new_I;

		for(auto i:I)
		{
			int left = i.first;
			int right = i.second;

			int lmid = int((left+right)/2);
			int rmid = lmid + 1;

			while(true)
			{
				pair<int,int> cur = get_ans(lmid);

				if(cur.first + cur.second == 0) return lmid;
				if(cur.first + cur.second == max_side) break;

				lmid--;
			}

			while(true)
			{
				pair<int,int> cur = get_ans(rmid);

				if(cur.first + cur.second == 0) return rmid;
				if(cur.first + cur.second == max_side) break;

				rmid++;
			}

			//cout << "LR: " << lmid << " " << rmid << endl;

			if(get_ans(lmid).first > get_ans(left).first) new_I.push_back({left,lmid});
			if(get_ans(right).first > get_ans(rmid).first) new_I.push_back({rmid,right});
		}

		I = new_I;
	}
}

#ifdef ARTHUR_LOCAL

	int main()
	{
		real_deal = {3,2,3,1,3,3,2,3};

		cout << find_best(8) << endl;
	}
#endif

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 696 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 680 KB Output is correct
7 Correct 4 ms 572 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 4 ms 632 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 3 ms 784 KB Output is correct
3 Correct 5 ms 700 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 14 ms 1084 KB Output is correct
12 Correct 10 ms 1196 KB Output is correct
13 Correct 14 ms 1176 KB Output is correct
14 Correct 50 ms 504 KB Output is correct
15 Incorrect 109 ms 1996 KB Incorrect
16 Halted 0 ms 0 KB -