oj.uz

Submission #596360

# Submission time Handle Problem Language Result Execution time Memory
596360 2022-07-14T15:57:06 Z angelo_torres Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

// x0 y0;
ll n,m,xo,yo;
ll xr,xl,yr,yl;

vpll goh(ll nx,ll ny){
	vpll rp = {{nx,ny}};
	for(ll i = 1; (nx + i*m <= n and i <= 2); ++i){
		cout << "examine " << nx + i*m << " " << ny << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx+i*m,ny});
	}
	for(ll i = 1; (nx - i*m >= 1 and i <= 2); ++i){
		cout << "examine " << nx - i*m << " " << ny << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx-i*m,ny});
	}
	sort(rp.begin(),rp.end());
	return rp;
}

vpll gov(ll nx,ll ny){
	vpll rp = {{nx,ny}};
	for(ll i = 1; (ny + i*m <= n and i <= 2); ++i){
		cout << "examine " << nx << " " << ny + i*m << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx,ny+i*m});
	}
	for(ll i = 1; (ny - i*m >= 1 and i <= 2); ++i){
		cout << "examine " << nx << " " << ny - i*m << endl;
		string ans; cin >> ans;
		if(ans == "true")
			rp.push_back({nx,ny-i*m});
	}
	sort(rp.begin(),rp.end());
	return rp;
}

int main(){
	cin >> n >> xo >> yo;
	ll l,r;
	l = xo, r = n+1;
	for(ll i = 0; xo + (1<<i) <= n; ++i){
		cout << "examine " << xo + (1<<i) << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = xo + (1<<i);
			break;
		}
	}
	while(r-l > 1){
		ll md = (l+r)>>1;
		cout << "examine " << md << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false")
			r = md;
		else
			l = md;
	}
	xr = l;
	l = xo, r = 0;
	for(ll i = 0; xo - (1<<i) >= 1; ++i){
		cout << "examine " << xo - (1<<i) << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = xo - (1<<i);
			break;
		}
	}
	while(l-r > 1){
		ll md = (l+r)>>1;
		cout << "examine " << md << " " << yo << endl;
		string ans; cin >> ans;
		if(ans == "false")
			r = md;
		else
			l = md;
	}
	xl = l;
	l = yo, r = n+1;
	for(ll i = 0; yo + (1<<i) <= n; ++i){
		cout << "examine " << xo << " " << yo + (1<<i) << endl;
		string ans; cin >> ans;
		if(ans == "false"){
			r = yo + (1<<i);
			break;
		}
	}
	while(r-l > 1){
		ll md = (l+r)>>1;
		cout << "examine " << xo << " " << md << endl;
		string ans; cin >> ans;
		if(ans == "false") 
			r = md;
		else 
			l = md;
	}
	yr = l;
	// yr-yl = xr-xl
	yl = xl-xr+yr;
	ll xc = (xl+xr)>>1, yc = (yl+yr)>>1;
	m = (xr-xl+1)<<1;
	vpll v = goh(xc,yc);
	if((ll) v.size() == 3){
		pll gr = v[1];
		vpll cl = gov(gr.first,gr.second);
		cout << "solution " << cl[1].first << " " << cl[1].second << endl;
	}
	else{
		ll anx = (v[0].first+v[1].first)>>1, any;
		vpll sv = gov(xc,yc);
		any = (sv[0].second+sv[1].second)>>1;
		cout << "solution " << anx << " " << any << endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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