Submission #257268

#	Time	Username	Problem	Language	Result	Execution time	Memory
257268		maximath_1	Colors (BOI20_colors)	C++11	100 / 100	3 ms	512 KiB

Colors

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <unordered_map>
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;

#define ll long long
unordered_map<ll, bool> vis;
ll n;
int resp;

int ask(ll x){
	printf("? %lld\n", x);
	fflush(stdout);
	scanf("%d", &resp);
	return resp;
}
void ans(ll x){
	printf("= %lld\n", x);
	fflush(stdout);
}

void solve(){
	scanf("%lld", &n);
	vis.clear();

	if(n == 2ll){
		resp = ask(1ll); resp = ask(2ll);
		if(resp) ans(1ll);
		else ans(2ll);
		return;
	}else if(n == 3ll){
		resp = ask(2ll); resp = ask(1ll);
		if(resp) ans(1ll);
		else{
			resp = ask(3ll);
			if(resp) ans(2ll);
			else ans(3ll);
		}
		return;
	}

	vector<ll> path_mid_to_hi;
	ll lf = 1ll, rg = n - 1ll;
	for(ll md; lf <= rg;){
		md = (lf + rg) / 2ll;
		path_mid_to_hi.push_back(md);
		if(lf == rg && md == n - 1ll) break;
		lf = md + 1ll;
	}

	ll st = n, bf = n;
	reverse(path_mid_to_hi.begin(), path_mid_to_hi.end());
	bool go_left = 1;
	for(ll i : path_mid_to_hi){
		bf = st;
		if(go_left) st -= i;
		else st += i;
		assert(!vis[st]);
		go_left ^= 1;
	}
	if(bf < st) go_left = 1;
	else go_left = 0;

	lf = 1ll, rg = n - 1ll;
	ll res = n;
	resp = ask(st);
	for(ll md; lf <= rg;){
		md = (lf + rg) / 2;
		if(go_left && st - md >= 1 && !vis[st - md]) st -= md;
		else{
			assert(st + md <= n && !vis[st + md]);
			st += md;
		}
		resp = ask(st);
		if(resp){
			res = md;
			rg = md - 1;
		}else lf = md + 1;
		go_left ^= 1;
	}

	ans(res);
	return;
}

int main(){
	int tc = 1;
	for(; tc --;) solve();
	return 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int ask(long long int)':
Colors.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &resp);
  ~~~~~^~~~~~~~~~~~~
Colors.cpp: In function 'void solve()':
Colors.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 33 / 33