Submission #102016

#	Time	Username	Problem	Language	Result	Execution time	Memory
102016		asifthegreat	Aliens (IOI07_aliens)	C++14	0 / 100	4 ms	384 KiB

aliens

#include <bits/stdc++.h>
#define int long long 
using namespace std;
 
char s[100];
int q = 0;
 
int n,lft,rght,mid;
 
bool valid(int x,int y)
{
  if(x <= 0 or y <= 0 or x > n or y > n)return false;
  return true;
}
 
bool query(int x,int y)
{
  if(!valid(x,y))return false;
  printf("examine %lld %lld\n",x,y);
  fflush(stdout);
  scanf("%s",s);
  if(s[0] == 't')return true;
  return false;
}
 
void anss(int a,int b)
{
  printf("solution %lld %lld\n",a,b);
  fflush(stdout);
}
 
int32_t main()
{
  int x,y,k;
  scanf("%lld %lld %lld",&n,&x,&y);
  int temp_x = x,temp_y = y;
 // while(1){
    //if(!query(temp_x+1ll,y))break;
    for(int i = 0; i <= 31;i++){
      if(temp_x+(1ll<<i) > n)break;
      if(query(temp_x+(1ll<<i),y)){
        temp_x += (1ll<<i);
      }
      else{
      	k = x+1ll<<i;break;
      }
    }
    // ebar temp_x theke k er moddhe ekta binary search kora lagbe ... 
    lft = temp_x;
    rght = k;
    mid;
    while(rght-lft>1){
    	mid = (lft+rght)>>1;
    	if(query(mid,y)){
    		lft = mid;
    	}
    	else{
    		rght = mid-1;
    	}
    }
    if(query(rght,y))temp_x = rght;
    else temp_x = lft;
  //}
  //cout << q << endl;
  //cout << temp_x << endl;
  int niche = temp_x;
  temp_x = x;
  //while(1){
    //if(!query(temp_x-1,y))break;
    for(int i = 0; i <= 31;i++){
      if(temp_x-(1ll<<i) <= 0)break;
      if(query(temp_x-(1ll<<i),y)){
        temp_x -= (1ll<<i);
      }
      else{
      	k = temp_x-(1ll<<i);
      }
    }
    lft = k;
    rght = temp_x;
    //int mid;
    while(rght-lft>1){
    	mid = (lft+rght)>>1;
    	if(query(mid,y)){
    		rght = mid;
    	}
    	else{
    		lft = mid+1;
    	}
    }
    if(query(lft,y))temp_x = lft;
    else temp_x = rght;
  //}
  //cout << q << endl;
  //cout << temp_x << endl;
  int upore = temp_x;
  //cout << niche  << " " << upore << endl;
  int expand = niche-upore+1;
  //cout << expand << endl;
  //while(1){
    //if(!query(x,temp_y+1ll))break;
    for(int i = 0; i <= 31;i++){
      //if(x+(1ll > n)break;
      if(temp_y+(1ll<<i) > n)break;
      if(query(x,temp_y+(1ll<<i))){
        temp_y += (1ll<<i);
      }
      else{
      	k = temp_y+(1ll<<i);break;
      }
    }
  //}
  lft = temp_x;
  rght = k;
    //int mid;
    while(rght-lft>1){
    	mid = (lft+rght)>>1;
    	if(query(x,mid)){
    		lft = mid;
    	}
    	else{
    		rght = mid-1;
    	}
    }
    if(query(x,rght))temp_y = rght;
    else temp_y = lft;
  int dan = temp_y;
  int bam = temp_y-expand+1;
  //{upore,niche,dan,bam roilo..}
  int per_upore = upore,per_niche = niche,per_dan = dan,per_bam = bam;
  //cout << q << endl;
  int uthlam = 0;
  while(1){
    if(!query(upore-1,bam-1))break;
    uthlam++;
    upore--,bam--;
    upore = upore-expand+1;
    bam = bam-expand+1;
    //cout << upore << " " << bam << endl;//exit(0);
  }
  if(uthlam >= 4){
    anss(upore+(expand*2)+(expand/2),bam+(expand*2)+(expand/2));
    exit(0);
  }
  int bame_gesi = 0;
  while(1){
    if(!query(upore,bam-expand-1))break;
    bam = bam-expand*2;
    bame_gesi++;
  }
  //cout << bam << endl;
  while(1){
    if(bame_gesi)break;
    if(!query(upore-expand-1,bam))break;
    upore = upore-expand*2;
  }
  anss(upore+(expand*2)+(expand/2),bam+(expand*2)+(expand/2));
 
  return 0;
    
}

Compilation message (stderr)

aliens.cpp: In function 'int32_t main()':
aliens.cpp:45:13: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
        k = x+1ll<<i;break;
            ~^~~~
aliens.cpp:51:8: warning: statement has no effect [-Wunused-value]
     mid;
        ^
aliens.cpp:130:7: warning: unused variable 'per_upore' [-Wunused-variable]
   int per_upore = upore,per_niche = niche,per_dan = dan,per_bam = bam;
       ^~~~~~~~~
aliens.cpp:130:25: warning: unused variable 'per_niche' [-Wunused-variable]
   int per_upore = upore,per_niche = niche,per_dan = dan,per_bam = bam;
                         ^~~~~~~~~
aliens.cpp:130:43: warning: unused variable 'per_dan' [-Wunused-variable]
   int per_upore = upore,per_niche = niche,per_dan = dan,per_bam = bam;
                                           ^~~~~~~
aliens.cpp:130:57: warning: unused variable 'per_bam' [-Wunused-variable]
   int per_upore = upore,per_niche = niche,per_dan = dan,per_bam = bam;
                                                         ^~~~~~~
aliens.cpp: In function 'bool query(long long int, long long int)':
aliens.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
   ~~~~~^~~~~~~~
aliens.cpp: In function 'int32_t main()':
aliens.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&n,&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:50:10: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
     rght = k;
     ~~~~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10