oj.uz

Submission #163314

# Submission time Handle Problem Language Result Execution time Memory
163314 2019-11-12T14:51:03 Z Berted Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 404 KB 
#include <iostream>
#define int long long
using namespace std;
int n,x,y,lf,rg,sz;
inline bool ask(int x,int y)
{
	if (y<1 || x<1 || x>n || y>n) {return 0;}
	else 
	{
		string rs;
		cout<<"examine "<<x<<" "<<y<<endl;
		cin>>rs;
		return rs=="true";
	}
}
int32_t main()
{	
	cin>>n>>x>>y;
	int l = 1,r = x;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(x-pv,y)) {l = pv+1;}
		else {r = pv;}
	}
	lf = x - (l - 1);
	l = x+1,r = n+1;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(pv,y)) {l = pv+1;}
		else {r = pv;}
	}
	rg = l - 1;
	//cout<<"RANDOM L R BOUND : "<<lf<<" "<<rg<<"\n";
	if (ask(lf - 2*(rg-lf+1),y) || ask(lf + 2*(rg-lf+1),y)) {sz = rg-lf+1;}
	else if ((rg-lf+1)%3==0 && (ask(lf - 2*(rg-lf+1)/3,y) || ask(lf + 2*(rg-lf+1)/3,y))) {sz = (rg-lf+1)/3;}
	else if ((rg-lf+1)%5==0 && (ask(lf - 2*(rg-lf+1)/5,y) || ask(lf + 2*(rg-lf+1)/5,y))) {sz = (rg-lf+1)/5;}
	//cout<<"SIZE FOUND TO BE : "<<sz<<"\n";
	int x1 = lf,y1 = y;
	while (true)
	{
		if (ask(x1 - sz,y1 - sz)) {x1 -= sz; y1 -= sz;}
		else if (ask(x1 - sz,y1 + sz)) {x1 -= sz; y1 += sz;}
		else {break;}
	}
	//cout<<"LOWEST X : "<<x1<<"\n";
	l = 1,r = y;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(x1,y-pv)) {l = pv+1;}
		else {r = pv;}
	}
	y1 = y - (l-1);
	//cout<<"RANDOM TOP Y : "<<y1<<"\n";
	while (true)
	{
		if (ask(x1 - sz,y1 - sz)) {x1 -= sz; y1 -= sz;}
		else if (ask(x1 + sz,y1 - sz)) {x1 += sz; y1 -= sz;}
		else {break;}
	}
	//cout<<"LOWEST Y : "<<y1<<"\n";
	cout<<"solution "<<x1 + 2*sz + sz/2<<" "<<y1 + 2*sz + sz/2<<endl;
	return 0;
}

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 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 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 248 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 3 ms 296 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 3 ms 248 KB Output is correct

Subtask #6
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 #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 3 ms 248 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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