oj.uz

Submission #168999

# Submission time Handle Problem Language Result Execution time Memory
168999 2019-12-17T12:52:59 Z Lawliet Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;

int n;

bool check(lli X, lli Y)
{
	if( X > n || Y > n ) return false;
	if( X <= 0 || Y <= 0 ) return false;

	cout << "examine " << X << " " << Y << endl;

	string s;
	cin >> s;

	return s[0] == 't';
}

pii bs(pii p, int dx, int dy)
{
	lli L = 0;
	lli R = n;

	lli X = p.first;
	lli Y = p.second;

	while( R - L > 1 )
	{
		lli m = ( L + R )/2;

		if( check( X + m*dx , Y + m*dy ) ) L = m;
		else R = m;
	}

	return { X + L*dx , Y + L*dy };
}

pii middleDiagonal(pii p, int dx, int dy)
{
	pii E1 = bs( p , dx , dy );
	pii E2 = bs( p , -dx , -dy );

	lli X = E1.first + E2.first;
	lli Y = E1.second + E2.second;

	return { X/2 , Y/2 };
}

int main()
{
	int X, Y;
	cin >> n >> X >> Y;

	pii curPoint = { X , Y };

	curPoint = bs( curPoint , -1 , 0 );
	curPoint = bs( curPoint , 0 , -1 );

	curPoint = middleDiagonal( curPoint , 1 , 1 );
	curPoint = middleDiagonal( curPoint , 1 , -1 );

	cout << "solution " << curPoint.first << " " << curPoint.second << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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