oj.uz

Submission #1017013

# Submission time Handle Problem Language Result Execution time Memory
1017013 2024-07-08T17:08:51 Z Nika533 Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 356 KB 
#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
int n,m,T,k,x,y;
//int arr[1005][1005];

int ask(int x, int y) {
	if (x<1 || x>m || y<1 || y>m) return 0;
	cout<<"examine "<<x<<" "<<y<<endl;
	string s; cin>>s;
	return (s=="true");
//	return arr[x][y];
}

//void sq(int x, int y) {
//	for (int i=x; i<x+n; i++) {
//		for (int j=y; j<y+n; j++) arr[i][j]=1;
//	}
//}
//
//void build() {
//	cin>>n>>x>>y;
//	int half=n/2;
//	for (int i=-2; i<=2; i++) {
//		for (int j=-2; j<=2; j++) {
//			if ((i+j+200)%2==0) sq(x-half+i*n,y-half+j*n);
//		}
//	}
//	for (int i=1; i<=50; i++) {
//		for (int j=1; j<=50; j++) cout<<arr[i][j];
//		cout<<endl;
//	}
//}

void test_case() {
	cin>>m>>x>>y;
	int l=0,r=2e9,xmax;
	while (l<=r) {
		int mid=(l+r)/2;
		int q1=ask(x+mid,y),q2=ask(x+mid/2,y),q3=ask(x+mid/4,y);
		if (q1 && q2 && q3) {
			xmax=x+mid; l=mid+1;
		}
		else {
			r=mid-1;
		}
	}
	x=xmax;
	l=0; r=2e9; int xmin;
	while (l<=r) {
		int mid=(l+r)/2;
		int q1=ask(x-mid,y),q2=ask(x-mid/2,y),q3=ask(x-mid/4,y);
		if (q1 && q2 && q3) {
			xmin=x-mid; l=mid+1;
		}
		else {
			r=mid-1;
		}
	}
	n=xmax-xmin+1;
	l=0; r=2e9; int ymax;
	while (l<=r) {
		int mid=(l+r)/2;
		int q1=ask(x,y+mid),q2=ask(x,y+mid/2),q3=ask(x,y+mid/4);
		if (q1 && q2 && q3) {
			ymax=y+mid; l=mid+1;
		}
		else {
			r=mid-1;
		}
	}
//	cout<<xmax<<" "<<ymax<<endl;
	int mnx=6,mny=6,mxx=-6,mxy=-6;
	for (int i=-4; i<=4; i++) {
		int xx=xmax+n*i,yy=ymax;
		int q=ask(xx,yy);
		if (q) {
			mnx=min(mnx,i);
			mxx=max(mxx,i);
		}
	}
	for (int i=-4; i<=4; i++) {
		int xx=xmax,yy=ymax+n*i;
		int q=ask(xx,yy);
		if (q) {
			mny=min(mny,i);
			mxy=max(mxy,i);
		}
	}
//	cout<<mnx<<" "<<mny<<" "<<mxx<<" "<<mxy<<endl; 
	int i1=mnx+2,i2=mny+2;
	if (mxx-mnx==2) {
		i1=mnx+1; i2=mny+1;
	}
//	cout<<i1<<" i "<<i2<<endl;
	int x2=xmax+n*i1,y2=ymax+n*i2;
	int half=n/2;
	cout<<"solution "<<x2-half<<" "<<y2-half<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; //build();
	while (T--) test_case();
}

Compilation message

aliens.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
aliens.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main () {
      | ^~~~
aliens.cpp: In function 'void test_case()':
aliens.cpp:105:19: warning: 'ymax' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |  int x2=xmax+n*i1,y2=ymax+n*i2;
      |                   ^~
aliens.cpp:69:8: warning: 'xmin' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |  n=xmax-xmin+1;
      |    ~~~~^~~~~
aliens.cpp:105:6: warning: 'xmax' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |  int x2=xmax+n*i1,y2=ymax+n*i2;
      |      ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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