Submission #642412

#	Time	Username	Problem	Language	Result	Execution time	Memory
642412		tolbi	Colors (BOI20_colors)	C++17	0 / 100	0 ms	208 KiB

Colors

#define author tolbi
#pragma optimize("Bismillahirrahmanirrahim")
#include <bits/stdc++.h>
#define int long long
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define ayahya() chrono::steady_clock().now().time_since_epoch().count()
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<bi)
const int MOD = 1e9+7;
using namespace std;
int N;
bool submitmode=true;
void prepare();
int ask(int n);
void final();
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		map<int,bool> mp;
		prepare();
		int n = N;
		if (n==1){
			cout<<"! "<<1<<endl;
			final();
			break;
		}
		else if (n==2){
			int noting = ask(1);
			int somting = ask(2);
			if (somting){
				cout<<"= 1"<<endl;
			}
			else cout<<"= 2"<<endl;
			final();
			break;
		}
		int l = 1, r = n;
		int crr = (n-(l+(r-l)/2))/2+1;
		ask(crr);
		int mv = 0;
		while (l < r){
			int mid = l+(r-l)/2;
			if (mv){
				mid*=-1;
			}
			if (mid>0) {
				while (crr+mid>n || mp[crr+mid]) {
					mid--;
				}
			}
			else {
				crr=max(1-mid,crr);
				while (crr+mid<1 || mp[crr+mid]) {
					mid++;
				}
			}
			mp[crr+mid]=true;
			if (ask(crr+mid)){
				if (mv) r=min(r,-mid);
				else r=min(r,mid);
			}
			else {
				if (mv) l=max(-mid+1,l);
				else l=max(l,mid+1);
			}
			crr+=mid;
			mv^=1;
		}
		cout<<"= "<<l<<endl;
		final();
	}
}
int c;
int last=ayahya();
int qc=0;
int ask(int n){
	if (submitmode){
		cout<<"? "<<n<<endl;
		deci(rv);
		return rv;
	}
	else {	
		if (n>N || n<1){
			cout<<n<<" "<<"LKAJSDLKASJDKLASDJKLASDHKJLSADHKLASJDHASKJDNASKLJDNASLKJDNKALJSDNK"<<endl;
		}
		qc++;
		cout<<"? "<<n<<endl;
		bool rv = (abs(last-n)>=c);
		cout<<rv<<endl;
		last=n;
		return rv;
	}
}
void prepare(){
	if (submitmode){
		cin>>N;
	}
	else {

		N=8654;
		c=3947;
		cout<<N<<endl;
	}
}
void final(){
	if (submitmode) return;
	cout<<"Answer = "<<c<<endl;
	cout<<"Query Count = "<<qc<<endl;
}

Compilation message (stderr)

Colors.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
Colors.cpp: In function 'int32_t main()':
Colors.cpp:38:8: warning: unused variable 'noting' [-Wunused-variable]
   38 |    int noting = ask(1);
      |        ^~~~~~

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