Submission #257265

#	Time	Username	Problem	Language	Result	Execution time	Memory
257265		maximath_1	Colors (BOI20_colors)	C++11	0 / 100	0 ms	256 KiB

Colors

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

#define ll long long
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);

	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;
		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;
		else 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; scanf("%d", &tc);
	for(; tc --;) solve();
	return 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int ask(long long int)':
Colors.cpp:16: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:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
Colors.cpp: In function 'int main()':
Colors.cpp:84:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int tc; scanf("%d", &tc);
          ~~~~~^~~~~~~~~~~

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