oj.uz

Submission #94611

# Submission time Handle Problem Language Result Execution time Memory
94611 2019-01-21T16:12:37 Z SuperJava Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 376 KB 
//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold

int main(){
	ll n,x1,y1;
	cin >> n >> x1 >> y1;
	ll nx,bx;
	ll l = x1,r = n;
	while(l < r){
		ll mid = (l+r+1)/2;
		cout << "examine " << mid << " " << y1 << endl;
		string ans;
		cin >> ans;
		if(ans == "true"){
			if(mid-l < 4){
				l = mid;
			}else{
				cout << "examine " << (mid+l)/2 << " " << y1 << endl;
				cin >> ans;
				if(ans == "true"){
					if((mid+l)/2-l < 4){
						l = (mid+l)/2;
					}else{
						cout << "examine " << (mid+(mid+l)/2)/2 << " " << y1 << endl;
						cin >> ans;
						if(ans == "true"){
							l = mid;
						}else{
							r = (mid+(mid+l)/2)/2-1;
						}
					}
				}else{
					r = (mid+l)/2-1;
				}
			}
		}else{
			r = mid-1;
		}
	}
	nx = l;
	l = 1;
	r = x1;
	while(l < r){
		ll mid = (l+r)/2;
		cout << "examine " << mid << " " << y1 << endl;
		string ans;
		cin >> ans;
		if(ans == "true"){
			if(r-mid < 4){
				r = mid;
			}else{
				cout << "examine " << (mid+r)/2 << " " << y1 << endl;
				cin >> ans;
				if(ans == "true"){
					if((mid+r)/2-l < 4){
						r = (mid+r)/2;
					}else{
						cout << "examine " << (mid+(mid+r)/2)/2 << " " << y1 << endl;
						cin >> ans;
						if(ans == "true"){
							r = mid;
						}else{
							l = (mid+(mid+r)/2)/2+1;
						}
					}
				}else{
					l = (mid+l)/2+1;
				}
			}
		}else{
			l = mid+1;
		}
	}
	bx = r;
	ll by,ny;
	l = y1;
	r = n;
	while(l < r){
		ll mid = (l+r+1)/2;
		cout << "examine " << x1 << " " << mid << endl;
		string ans;
		cin >> ans;
		if(ans == "true"){
			if(mid-l < 4){
				l = mid;
			}else{
				cout << "examine " << x1 << " " << (mid+l)/2 << endl;
				cin >> ans;
				if(ans == "true"){
					if((mid+l)/2-l < 4){
						l = (mid+l)/2;
					}else{
						cout << "examine " << x1 << " " << (mid+(mid+l)/2)/2 << endl;
						cin >> ans;
						if(ans == "true"){
							l = mid;
						}else{
							r = (mid+(mid+l)/2)/2-1;
						}
					}
				}else{
					r = (mid+l)/2-1;
				}
			}
		}else{
			r = mid-1;
		}
	}
	ny = r;
	l = 1;
	r = y1;
	while(l < r){
		ll mid = (l+r)/2;
		cout << "examine " << x1 << " " << mid << endl;
		string ans;
		cin >> ans;
		if(ans == "true"){
			if(r-mid < 4){
				r = mid;
			}else{
				cout << "examine " << x1 << " " << (mid+r)/2 << endl;
				cin >> ans;
				if(ans == "true"){
					if((mid+r)/2-l < 4){
						r = (mid+r)/2;
					}else{
						cout << "examine " << x1 << " " << (mid+(mid+r)/2)/2 << endl;
						cin >> ans;
						if(ans == "true"){
							r = mid;
						}else{
							l = (mid+(mid+r)/2)/2+1;
						}
					}
				}else{
					l = (mid+l)/2+1;
				}
			}
		}else{
			l = mid+1;
		}
	}
	by = r;
	ll m = nx-bx+1;
	x1 = (bx+nx)/2;
	y1 = (by+ny)/2;
	ll q = 0, w = 0;
	while(x1-(q+1)*m >= 1 && y1-(q+1)*m >= 1){
		cout << "examine " << x1-(q+1)*m << " " << y1-(q+1)*m << endl;
		string ans; cin >> ans;
		if(ans == "true") q++;
		else break;
	}
	while(x1+(w+1)*m <= n && y1+(w+1)*m <= n){
		cout << "examine " << x1+(w+1)*m << " " << y1+(w+1)*m << endl;
		string ans; cin >> ans;
		if(ans == "true") w++;
		else break;
	}
	x1 += (w-q)/2*m;
	y1 += (w-q)/2*m;
	q = w = 0;
	while(x1-(q+1)*m >= 1 && y1+(q+1)*m <= n){
		cout << "examine " << x1-(q+1)*m << " " << y1+(q+1)*m << endl;
		string ans; cin >> ans;
		if(ans == "true") q++;
		else break;
	}
	while(x1+(w+1)*m <= n && y1-(w+1)*m >= 1){
		cout << "examine " << x1+(w+1)*m << " " << y1-(w+1)*m << endl;
		string ans; cin >> ans;
		if(ans == "true") w++;
		else break;
	}
	x1 += (w-q)/2*m;
	y1 -= (w-q)/2*m;
	cout << "solution " << x1 << " " << y1 << 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 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 248 KB Output is correct

Subtask #3
10.0 / 10.0

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

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

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

Subtask #7
10.0 / 10.0

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

Subtask #8
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
3 Correct 4 ms 376 KB Output is correct

Subtask #9
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 2 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 4 ms 376 KB Output is correct
3 Correct 3 ms 248 KB Output is correct