oj.uz

Submission #226511

# Submission time Handle Problem Language Result Execution time Memory
226511 2020-04-24T05:47:36 Z bensonlzl Aliens (IOI07_aliens) C++14
100 / 100
 7 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;

ll N, X, Y, M, cenX, cenY;
ll gap, upper, lefter, righter, lower;
ll tl = 1, tr = 1, bl = 1, br = 1;

map<pii,pi> grid; // (tl,tr,bl,br) -> (dx,dy)

int examine(int x, int y){
	if (1 > x || 1 > y || x > N || y > N) return 0;
	string res;
	cout << "examine " << x << ' ' << y << '\n' << flush;
	cin >> res;
	return (res == "true");
}

void solveUp(){
	gap = 1;
	while (1){
		int k = examine(X,Y+gap);
		if (k) gap *= 2;
		else break;
	}
	for (int i = 31; i >= 0; --i){
		if (upper+(1ll << i) >= gap) continue;
		if (examine(X,Y+(upper+(1ll << i)))){
			upper += (1ll << i);
		}
	}
	//cerr << upper << '\n';
}

void solveDown(){
	gap = 1;
	while (1){
		int k = examine(X,Y-gap);
		if (k) gap *= 2;
		else break;
	}
	for (int i = 31; i >= 0; --i){
		if (lower+(1ll << i) >= gap) continue;
		if (examine(X,Y-(lower+(1ll << i)))){
			lower += (1ll << i);
		}
	}
	//cerr << lower << '\n';
}

void solveLeft(){
	gap = 1;
	while (1){
		int k = examine(X-gap,Y);
		if (k) gap *= 2;
		else break;
	}
	for (int i = 31; i >= 0; --i){
		if (lefter+(1ll << i) >= gap) continue;
		if (examine(X-(lefter+(1ll << i)),Y)){
			lefter += (1ll << i);
		}
	}
	//cerr << lefter << '\n';
}

void solveRight(){
	gap = 1;
	while (1){
		int k = examine(X+gap,Y);
		if (k) gap *= 2;
		else break;
	}
	for (int i = 31; i >= 0; --i){
		if (righter+(1ll << i) >= gap) continue;
		if (examine(X+(righter+(1ll << i)),Y)){
			righter += (1ll << i);
		}
	}
	//cerr << righter << '\n';
}

void init(){
	grid[pii(pi(0,4),pi(0,0))] = pi(2,2);
	grid[pii(pi(2,2),pi(0,0))] = pi(0,2);
	grid[pii(pi(4,0),pi(0,0))] = pi(-2,2);

	grid[pii(pi(1,3),pi(1,1))] = pi(1,1);
	grid[pii(pi(3,1),pi(1,1))] = pi(-1,1);

	grid[pii(pi(0,2),pi(0,2))] = pi(2,0);
	grid[pii(pi(2,2),pi(2,2))] = pi(0,0);
	grid[pii(pi(2,0),pi(2,0))] = pi(-2,0);

	grid[pii(pi(1,1),pi(1,3))] = pi(1,-1);
	grid[pii(pi(1,1),pi(3,1))] = pi(-1,-1);

	grid[pii(pi(0,0),pi(0,4))] = pi(2,-2);
	grid[pii(pi(0,0),pi(2,2))] = pi(0,-2);
	grid[pii(pi(0,0),pi(4,0))] = pi(-2,-2);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	init();
	cin >> N >> X >> Y;
	solveUp();
	solveDown();
	solveLeft();
	solveRight();
	assert(lefter + righter == upper + lower);
	M = lefter + righter + 1;
	cenX = X - ((M-1)/2 - righter);
	cenY = Y - ((M-1)/2 - upper);
	while (1){
		if (examine(X-M*tl,Y+M*tl)) tl++;
		else break; 
	}
	while (1){
		if (examine(X+M*tr,Y+M*tr)) tr++;
		else break; 
	}
	while (1){
		if (examine(X-M*bl,Y-M*bl)) bl++;
		else break; 
	}
	while (1){
		if (examine(X+M*br,Y-M*br)) br++;
		else break; 
	}
	tl--; tr--; bl--; br--;
	pi delta = grid[pii(pi(tl,tr),pi(bl,br))];
	//cerr << tl << ' ' << tr << ' ' << bl << ' ' << br << '\n';
	//cerr << delta.first << ' ' << delta.first << '\n';
	cout << "solution " << cenX + delta.first * M << ' '  << cenY + delta.second * M << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 308 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #10
10.0 / 10.0

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