Submission #533053

#	Time	Username	Problem	Language	Result	Execution time	Memory
533053		chaoyue	Aliens (IOI07_aliens)	C++17	0 / 100	1 ms	200 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n, xo, yo, tops, bottoms, lefts, rights, cx, cy, length;
int c, var, m, mm, mmm;  //c is constant, var is shiftable coordinate
bool vertical;  //whether analysing vertical

bool examine(int a){
	string s;
	if(vertical){
		cout<<"examine "<<xo<<" "<<a<<flush;
	}
	else{
		cout<<"examine "<<a<<" "<<yo<<flush;
	}
	cin>>s;
	if(s == "true") return 1;
	return 0;
}

bool query(int x, int y){
	string s;
	cout<<"examine "<<x<<" "<<y<<flush;
	cin>>s;
	if(s == "true") return 1;
	return 0;
}

void bs(){  //inital binary search
	while(true){
		m = (c+var)/2;
		if(examine(m)) break;
		var = m;
	}
}

int getcase(){  //1 -> is first square, 2 -> is second square, 3 -> is third square
	mm = (c+m)/2;
	mmm = (c+mm)/2;
	if(!examine(mm)){
		return 2;
	}
	else{
		if(examine(mmm)) return 1;
		return 3;
	}
}

int bs2(int l, int r){
	if(l > r) swap(l, r);
	while(r-l > 1){
		int mid = (l+r)/2;
		if(examine(mid)){
			if(var > c){
				l = mid;
			}
			else{
				r = mid;
			}
		}
		else{
			if(var > c){
				r = mid;
			}
			else{
				l = mid;
			}
		}
	}
	if(var > c) return l;
	return r;
}

int side(int C, int VAR, bool VERTICAL){
	int square;
	vertical = VERTICAL;
	c = C;
	var = VAR;
	bs();
	square = getcase();
	if(square == 2){
		return bs2(c, mm);
	}
	else if(square == 1){
		return bs2(m, var);
	}
	else{
		return bs2(c, mmm);
	}
}

int diag(int hor, int ver){
	int newx, newy;
	for(int i=1; i<=4; i++){
		newx = cx + hor * i * length;
		newy = cy + ver * i * length;
		if(newx <= 0 || newx > n || newy <= 0 || newy > n || !query(newx, newy)) return i-1;
	}
	return 4;
}

void solve(){
	rights = side(xo, n+1, 0);
	lefts = side(xo, -1, 0);
	tops = side(yo, n+1, 1);
	bottoms = side(yo, -1, 1);
	length = rights - lefts + 1;
	cx = (lefts + rights)/2;
	cy = (bottoms + tops)/2;
	while(1){
		
	}
	int tl, tr, bl, br;
	tl = diag(-1, 1);
	tr = diag(1, 1);
	bl = diag(-1, -1);
	br = diag(1, -1);
	cx += (br - tl + tr - bl) / 2 * length;
	cy += (tl - br + tr - bl) / 2 * length;
	cout<<"solution "<<cx<<" "<<cy<<flush;
}

int main(){
	cin>>n>>xo>>yo;
	solve();
	return 0;
}

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