제출 #292837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292837		crackersamdjam	Colors (BOI20_colors)	C++17	0 / 100	0 ms	256 KiB

Colors

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
using ll = long long;

ll n;

#ifndef ONLINE_JUDGE
ll last, C = 4;
bool ask(ll a){
	cout<<"? "<<a<<endl;
	assert(a > 0 and a <= n);
	bool ret = abs(last-a) <= C;
	last = a;
	pr("ret", ret);
	return ret;
}
#else
bool ask(ll a){
	assert(a > 0 and a <= n);
	cout<<"? "<<a<<endl;
	bool x;
	cin>>x;
	return x;
}
#endif

int main(){
	cin>>n;
	ll st = 1, dir = 1;
	ll l = 2, m, r = n-1;
	while(l <= r){
		m = (l+r)/2;
		pr(m*dir);
		st += dir*m;
		dir = -dir;
		l = m+1;
	}
	ll off = n-st;
	//offset (increase starting point by this)
	if(dir == 1){ //last one was negative
		st = n-(1-st);
		off = n-st;
		pr("rev");
	}

	int i = off+1;
	pr("st i", st, i);
	dir = 1;
	ask(i); //init
	l = 2, r = n-1;
	while(l <= r){
		m = (l+r)/2;

		i += dir*m;
		dir = -dir;

		if(ask(i))
			l = m+1;
		else
			r = m-1;
	}
	assert(r > 0 and r <= n);
	cout<<"= "<<r<<endl;
}
/*
alternate l/r jumps
if ans <= m, then works
otherwise, don't run out of space
precalc starting point in reverse
*/

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