Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
1,049
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string s;
  6. int no,zero,one;
  7. int n;
  8.  
  9. int query(string x)
  10. {
  11.     cout << "? " << x << endl; cout.flush();
  12.     int ans;
  13.     cin >> ans;
  14.     return n-ans;
  15. }
  16.  
  17.  
  18. int query(int st,int en)
  19. {
  20.     string x=s;
  21.     int i;
  22.     for(i=st;i<=en;i++)
  23.         x[i]='0';
  24.     return query(x);
  25. }
  26.  
  27. void go0(int x,int y)
  28. {
  29.     if(x==y)
  30.     {
  31.         zero=x;
  32.         return;
  33.     }
  34.     int mid=(x+y)/2;
  35.     int ans=query(x,mid)-no;
  36.     if(ans!=-(mid-x+1))
  37.         go0(x,mid);
  38.     else
  39.         go0(mid+1,y);
  40. }
  41.  
  42. void go1(int x,int y)
  43. {
  44.     if(x==y)
  45.     {
  46.         one=x;
  47.         return;
  48.     }
  49.     int mid=(x+y)/2;
  50.     int ans=query(x,mid)-no;
  51.     if(ans!=(mid-x+1))
  52.         go1(x,mid);
  53.     else
  54.         go1(mid+1,y);
  55. }
  56. void go(int x,int y)
  57. {
  58.     int mid=(x+y)/2;
  59.     int ans=query(x,mid)-no;
  60.     if(ans==-(mid-x+1))
  61.     {
  62.         one=x; go0(mid+1,y);
  63.     }
  64.     else if(ans==(mid-x+1))
  65.     {
  66.         zero=x; go1(mid+1,y);
  67.     }
  68.     else
  69.     {
  70.         go(x,mid);
  71.     }
  72. }
  73.  
  74. int main()
  75. {
  76.     cin >> n;
  77.     s=string(n,'1');
  78.     no=query(s);
  79.     go(0,n-1);
  80.     cout << "! " << zero+1 << " " << one+1 << endl; cout.flush();
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement