oj.uz

답안 #533041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533041 2022-03-04T14:38:21 Z chaoyue Aliens (IOI07_aliens) C++17
0 / 100
 1 ms 288 KB 
#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;
	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;
}

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 0 ms 288 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -