oj.uz

Submission #533154

# Submission time Handle Problem Language Result Execution time Memory
533154 2022-03-05T02:13:06 Z chaoyue Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 308 KB 
#include <bits/stdc++.h>
using namespace std;

#define int 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<<endl;
	}
	else{
		cout<<"examine "<<a<<" "<<yo<<endl;
	}
	cin>>s;
	if(s == "true") return 1;
	return 0;
}

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

void bs(){  //inital binary search
	while(1){
		m = (c+var)/2;
		if(var < c) m++;
		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, 0, 0);
	tops = side(yo, n+1, 1);
	bottoms = side(yo, 0, 1);
	length = rights - lefts + 1;
	cx = (lefts + rights)/2;
	cy = (bottoms + tops)/2;
	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<<endl;
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 308 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct