fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. #define ld long double
  9. #define ll long long
  10. #define pb push_back
  11. #define fin(a, n) for(int i = a; i < n; i++)
  12. #define fjn(a, n) for(int j = a; j < n; j++)
  13. #define all(a) a.begin(),a.end()
  14. #define allr(a) a.rbegin(),a.rend()
  15. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  16.  
  17. using namespace std;
  18.  
  19. const double PI = acos(-1);
  20. const int N = 1e5 + 10, M = 1e3 + 10, LOG = 20;
  21. const ll oo = 0x3f3f3f3f3f3f3f3f;
  22. const int mod = 998244353, inf = 1e6;
  23. const ld EPS = 1e-9;
  24.  
  25. string di[] = {"D", "L", "U", "R", "UL", "UR", "DL", "DR"};
  26. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  27. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  28. char dc[] = {'D', 'L', 'R', 'U'};
  29.  
  30. int n;
  31. vector<int> ans;
  32. vector<vector<char>> chars;
  33.  
  34. char ask(int i, int j) {
  35.     if (chars[i][j] != '&') return chars[i][j];
  36.     cout << "? " << i << " " << j << endl;
  37.     cout.flush();
  38.     char c; cin >> c;
  39.     chars[i][j] = c;
  40.     return c;
  41. }
  42.  
  43. void solve(vector<int> &nuts, vector<int> &bolts) {
  44.     if (nuts.empty()) return;
  45.     if (nuts.size() == 1) {
  46.         ans[nuts[0]] = bolts[0];
  47.         return;
  48.     }
  49.  
  50.     int r = rand() % nuts.size();
  51.     swap(nuts[0], nuts[r]);
  52.  
  53.     vector<int> big, small;
  54.     int same = -1;
  55.     for (int b : bolts) {
  56.         char c = ask(nuts[0], b);
  57.  
  58.         if (c == '<') big.push_back(b);
  59.         else if (c == '>') small.push_back(b);
  60.         else same = b, ans[nuts[0]] = b;
  61.     }
  62.  
  63.     vector<int> small2, big2;
  64.     for (int i = 0; i < nuts.size(); i++) {
  65.         char c = ask(nuts[i], same);
  66.         if (c == '=') continue;
  67.         if (c == '>') big2.push_back(nuts[i]);
  68.         else small2.push_back(nuts[i]);
  69.     }
  70.     solve(small2, small);
  71.     solve(big2, big);
  72. }
  73.  
  74. void solve() {
  75.     cin >> n;
  76.     ans.assign(n+1, 0);
  77.     vector<int> nuts, bolts;
  78.     for (int i = 1; i <= n; i++) nuts.pb(i), bolts.pb(i);
  79.     chars = vector<vector<char>>(n+1, vector<char>(n+1, '&'));
  80.     solve(nuts, bolts);
  81.     cout << "! ";
  82.     for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  83.     cout << endl;
  84. }
  85.  
  86. int main() {
  87.     FAST;
  88. // #ifndef ONLINE_JUDGE
  89. //     freopen("input.txt", "r",stdin);
  90. //     freopen("output.txt", "w",stdout);
  91. // #endif
  92.     int tt = 1, c = 1; //cin >> tt;
  93.     while (tt--) {
  94.         // cout << "Case " << c++ << ":\n";
  95.         solve();
  96.     }
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
!
https://ideone.com/Cu8vST
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!