oj.uz

Submission #557102

# Submission time Handle Problem Language Result Execution time Memory
557102 2022-05-04T18:09:36 Z aryan12 Colors (BOI20_colors) C++17
0 / 100
 1 ms 316 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
	int n;
	cin >> n;
	if(n == 2)
	{
		cout << "? 1" << endl;
		int reply;
		cin >> reply;
		cout << "? 2" << endl;
		cin >> reply;
		reply = 1 - reply;
		cout << "= " << reply + 1 << endl;
		return;
	}
	int reply;
	cout << "? " << 3 * n / 4 << endl;
	cin >> reply;
	cout << "? " << n / 4 << endl;
	cin >> reply;
	set<int> already_replied;
	already_replied.insert(3 * n / 4);
	already_replied.insert(n / 4);
	int value = (3 * n / 4) - (n / 4);
	int to_check = value;
	if(reply == 0)
	{
		to_check += value / 2;
	}
	else
	{
		to_check -= value / 2;
	}
	// cout << "value = " << value << ", to_check = " << to_check << endl;
	int queries = 2;
	int current_value = n / 4;
	int final_answer = (reply == 0) ? n : (3 * n / 4 - n / 4);
	while(true)
	{
		queries++;
		if(queries == 65)
		{
			break;
		}
		// cout << "current to check is: " << to_check << endl;
		int to_the_left = current_value - to_check;
		int to_the_right = current_value + to_check;
		if(already_replied.count(to_the_left) || to_the_left <= 0)
		{
			if(already_replied.count(to_the_right) || to_the_right > n)
			{
				for(int i = 1; i <= n; i++)
				{
					if(!already_replied.count(i))
					{
						cout << "? " << i << endl;
						cin >> reply;
						current_value = i;
						already_replied.insert(i);
						break;
					}
				}
			}
			else
			{
				cout << "? " << to_the_right << endl;
				already_replied.insert(to_the_right);
				cin >> reply;
				value /= 2;
				current_value = to_the_right;
				if(reply == 0)
				{
					to_check += value / 2;
				}
				else
				{
					final_answer = to_check;
					to_check -= value / 2;
				}
			}
		}
		else
		{
			cout << "? " << to_the_left << endl;
			already_replied.insert(to_the_left);
			cin >> reply;
			value /= 2;
			current_value = to_the_left;
			if(reply == 0)
			{
				to_check += value / 2;
			}
			else
			{
				final_answer = to_check;
				to_check -= value / 2;
			}
		}
	}
	cout << "= " << final_answer << endl;
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB OK (7 queries)
2 Correct 1 ms 316 KB OK (49 queries)
3 Correct 1 ms 208 KB OK (10 queries)
4 Incorrect 1 ms 208 KB Wrong guess
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB OK (7 queries)
2 Correct 1 ms 316 KB OK (49 queries)
3 Correct 1 ms 208 KB OK (10 queries)
4 Incorrect 1 ms 208 KB Wrong guess
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB OK (7 queries)
2 Correct 1 ms 316 KB OK (49 queries)
3 Correct 1 ms 208 KB OK (10 queries)
4 Incorrect 1 ms 208 KB Wrong guess
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB OK (7 queries)
2 Correct 1 ms 316 KB OK (49 queries)
3 Correct 1 ms 208 KB OK (10 queries)
4 Incorrect 1 ms 208 KB Wrong guess
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB OK (7 queries)
2 Correct 1 ms 316 KB OK (49 queries)
3 Correct 1 ms 208 KB OK (10 queries)
4 Incorrect 1 ms 208 KB Wrong guess
5 Halted 0 ms 0 KB -