oj.uz

Submission #120367

# Submission time Handle Problem Language Result Execution time Memory
120367 2019-06-24T09:07:02 Z baluteshih Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 412 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll n;

ll query(ll x,ll y)
{
	if(x<=0||y<=0||x>n||y>n) return 0;
	cout << "examine " << x << " " << y << endl;
	string s;
	cin >> s;
	return (s[0]=='t');
}
 
int main()
{
	ll x,y,L,R,l,r,dis,m;
	cin >> n >> x >> y;
	l=x,r=n+1;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(mid,y)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=0,r=x;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(mid,y)==0) l=mid;
		else r=mid-1;
	}
	L=l,dis=R-L-1;
	//cout << "part2: " << L << " " << R << endl;
	ll c=L+R>>1,cx,cy;
	if(query(c,y)==0) m=dis/3;
	else if(dis%5==0)
		if(query(c+dis/5,y)==0) m=dis/5;
		else m=dis;
	else m=dis;
	//cout << "part3: " << m << endl;
	l=x,r=x+m;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(mid,y)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=x-m,r=x;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(mid,y)==0) l=mid;
		else r=mid-1;
	}
	L=l,cx=L+R>>1;
	//cout << "part4: " << cx << endl;
	l=y,r=y+m;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(cx,mid)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=y-m,r=y;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(cx,mid)==0) l=mid;
		else r=mid-1;
	}
	L=l,cy=L+R>>1;
	//cout << "part5: " << cy << endl;
	l=query(cx,cy+2*m)+query(cx,cy+4*m);
	r=query(cx,cy-2*m)+query(cx,cy-4*m);
	if(l+r==2)
		if(l==2) cy+=2*m;
		else if(r==2) cy-=2*m;
		else;
	else
		if(l==1) cy+=m,cx+=m;
		else cy-=m,cx+=m;
	
	c=query(cx+2*m,cy)+query(cx+4*m,cy);
	if(c==2) cx+=2*m;
	else if(c==0) cx-=2*m;
	
	cout << "solution " << cx << " " << cy << endl;
}

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:34:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:47:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll c=L+R>>1,cx,cy;
       ~^~
aliens.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:68:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  L=l,cx=L+R>>1;
         ~^~
aliens.cpp:73:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:84:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  L=l,cy=L+R>>1;
         ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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