Submission #596360

#	Time	Username	Problem	Language	Result	Execution time	Memory
596360		angelo_torres	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	292 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

// x0 y0;
ll n,m,xo,yo;
ll xr,xl,yr,yl;

vpll goh(ll nx,ll ny){
	vpll rp = {{nx,ny}};
	for(ll i = 1; (nx + i*m <= n and i <= 2); ++i){
		cout << "examine " << nx + i*m << " " << ny << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx+i*m,ny});
	}
	for(ll i = 1; (nx - i*m >= 1 and i <= 2); ++i){
		cout << "examine " << nx - i*m << " " << ny << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx-i*m,ny});
	}
	sort(rp.begin(),rp.end());
	return rp;
}

vpll gov(ll nx,ll ny){
	vpll rp = {{nx,ny}};
	for(ll i = 1; (ny + i*m <= n and i <= 2); ++i){
		cout << "examine " << nx << " " << ny + i*m << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx,ny+i*m});
	}
	for(ll i = 1; (ny - i*m >= 1 and i <= 2); ++i){
		cout << "examine " << nx << " " << ny - i*m << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx,ny-i*m});
	}
	sort(rp.begin(),rp.end());
	return rp;
}

int main(){
	cin >> n >> xo >> yo;
	ll l,r;
	l = xo, r = n+1;
	for(ll i = 0; xo + (1<<i) <= n; ++i){
		cout << "examine " << xo + (1<<i) << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = xo + (1<<i);
			break;
		}
	}
	while(r-l > 1){
		ll md = (l+r)>>1;
		cout << "examine " << md << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false")
			r = md;
		else
			l = md;
	}
	xr = l;
	l = xo, r = 0;
	for(ll i = 0; xo - (1<<i) >= 1; ++i){
		cout << "examine " << xo - (1<<i) << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = xo - (1<<i);
			break;
		}
	}
	while(l-r > 1){
		ll md = (l+r)>>1;
		cout << "examine " << md << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false")
			r = md;
		else
			l = md;
	}
	xl = l;
	l = yo, r = n+1;
	for(ll i = 0; yo + (1<<i) <= n; ++i){
		cout << "examine " << xo << " " << yo + (1<<i) << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = yo + (1<<i);
			break;
		}
	}
	while(r-l > 1){
		ll md = (l+r)>>1;
		cout << "examine " << xo << " " << md << endl;
		string ans; cin >> ans;
		if(ans == "false") 
			r = md;
		else 
			l = md;
	}
	yr = l;
	// yr-yl = xr-xl
	yl = xl-xr+yr;
	ll xc = (xl+xr)>>1, yc = (yl+yr)>>1;
	m = (xr-xl+1)<<1;
	vpll v = goh(xc,yc);
	if((ll) v.size() == 3){
		pll gr = v[1];
		vpll cl = gov(gr.first,gr.second);
		cout << "solution " << cl[1].first << " " << cl[1].second << endl;
	}
	else{
		ll anx = (v[0].first+v[1].first)>>1, any;
		vpll sv = gov(xc,yc);
		any = (sv[0].second+sv[1].second)>>1;
		cout << "solution " << anx << " " << any << endl;
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10