Submission #596349

#	Time	Username	Problem	Language	Result	Execution time	Memory
596349		angelo_torres	Aliens (IOI07_aliens)	C++17	80 / 100	2 ms	296 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
typedef vector<ii> vii;

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

vii goh(int nx,int ny){
	vii rp = {{nx,ny}};
	for(int 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(int 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;
}

vii gov(int nx,int ny){
	vii rp = {{nx,ny}};
	for(int 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(int 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;
	int l,r;
	l = xo, r = n+1;
	for(int 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){
		int 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(int 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){
		int 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(int 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){
		int 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;
	int xc = (xl+xr)>>1, yc = (yl+yr)>>1;
	m = (xr-xl+1)<<1;
	vii v = goh(xc,yc);
	if((int) v.size() == 3){
		ii gr = v[1];
		vii cl = gov(gr.first,gr.second);
		cout << "solution " << cl[1].first << " " << cl[1].second << endl;
	}
	else{
		int anx = (v[0].first+v[1].first)>>1, any;
		vii 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: 0 / 10
• Subtask 10: 0 / 10