Advertisement
Guest User

Untitled

a guest
Sep 16th, 2018
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <array>
  5. #include <list>
  6. #include <stack>
  7. #include <queue>
  8. #include <deque>
  9. #include <map>
  10. #include <set>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13. #include <algorithm>
  14. #include <functional>
  15. #include <random>
  16. #include <limits>
  17. #include <string>
  18. #include <sstream>
  19. #include <numeric>
  20.  
  21. #include <cassert>
  22. #include <cmath>
  23. #include <ctime>
  24.  
  25. using namespace std;
  26.  
  27. #pragma comment(linker, "/STACK:200000000")
  28.  
  29. const int param = 17, siz = 1000, len = 400;
  30.  
  31. int ask (int a, int b)
  32. {
  33. if (b < a)
  34. return ask (b + 1, a + 1);
  35.  
  36. static vector<vector<int>> dp (siz + 1, vector<int> (siz + 1, -1));
  37.  
  38. if (dp[a][b] == -1)
  39. {
  40. cout << "? " << a + 1 << ' ' << b << endl;
  41. cout.flush ();
  42.  
  43. cin >> dp[a][b];
  44. }
  45.  
  46. return dp[a][b];
  47. }
  48.  
  49. void solve (istream &cin = std::cin, ostream &cout = std::cout)
  50. {
  51. string str (siz, '0');
  52.  
  53. for (int i = 0; i < str.size (); i++)
  54. {
  55. int one = 0, zer = 0;
  56. const int ev = 4;
  57.  
  58. for (int j = 0; one < ev && zer < ev; j++)
  59. {
  60. int big, small;
  61.  
  62. if (i < siz / 2)
  63. {
  64. big = ask (i, i + len + j);
  65. small = ask (i + 1, i + len + j);
  66. }
  67. else
  68. {
  69. big = ask (i - len - j, i + 1);
  70. small = ask (i - len - j, i);
  71. }
  72.  
  73.  
  74. if (big == small + 1)
  75. one++;
  76. else if (big == small)
  77. zer++;
  78. }
  79.  
  80. if (one > zer)
  81. str[i] = '1';
  82. }
  83.  
  84. cout << "! " << str << endl;
  85. }
  86.  
  87.  
  88. int main ()
  89. {
  90. #ifdef LOCAL
  91. solve ();
  92.  
  93. cout << "clock: " << clock () / (double)CLOCKS_PER_SEC << endl;
  94. #else
  95. solve ();
  96. #endif
  97.  
  98. return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement