knightL

CF D with interactor

Oct 17th, 2021
1,026
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstring>
  4. #include <iomanip>
  5. #include <string>
  6. #include <stdio.h>
  7. #include <math.h>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <stack>
  13. #include <queue>
  14. #include <cassert>
  15. using namespace std;
  16. //types
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef map <string, ll> msi;
  20. typedef map <char, ll> mci;
  21. typedef map <ll, ll> mii;
  22. typedef set <ll> si;
  23. typedef pair <ll, ll> pii;
  24. typedef set <char> schar;
  25. typedef vector <ll> vi;
  26. typedef vector <vi> vvi;
  27. typedef vector <ld> vld;
  28. typedef vector <pii> vpii;
  29. // loops
  30. #define FOR(i,a,b) for (ll i = (a); i < (b); i++)
  31. #define F0R(i,a) FOR(i,0,a)
  32. #define ROF(i,a,b) for (ll i = (b)-1; i >= (a); i--)
  33. #define R0F(i,a) ROF(i,0,a)
  34. #define rep(a) F0R(__,a)
  35. #define each(a,x) for (auto& a: x)
  36. #define scan(x) each (a, x) cin >> a;
  37. #define scanp(x) each (p, x) cin >> p.fs >> p.sc;
  38. #define print(x) each (a, x) cout << a << ' ';
  39. // other
  40. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(9);
  41. #define _ << " "
  42. #define all(x) (x).begin(), (x).end()
  43. #define rall(x) (x).rbegin(), (x).rend()
  44. #define mp make_pair
  45. #define fs first
  46. #define sc second
  47. #define pb push_back
  48.  
  49. void solve();
  50. void solvet() {
  51.     int t; cin >> t;
  52.     rep(t) solve();
  53. }
  54. int main() {
  55.     IOS;
  56.     cout << setprecision(20);
  57.     solve();
  58.     return 0;
  59. }
  60.  
  61. ll autoGetAns(vector<int> q)
  62. {
  63.     for(int i: q)
  64.         assert( 0<i && i<=q.size());
  65.  
  66.     vector<int> p{12,6,2,3,11,4,1,7,8,5,10,9};
  67.     assert(q.size() == p.size());
  68.     vector<int> s(q);
  69.     for(int i=0;i<p.size();i++)
  70.     {
  71.         s[i] += p[i];
  72.     }
  73.     map<int,int> cnt;
  74.     for(int i=0;i<p.size();i++)
  75.         cnt[s[i]]++;
  76.     ll res = 0;
  77.    
  78.     for(int i=0;i<p.size();i++)
  79.         if(cnt[s[i]] > 1 )
  80.         {
  81.             res=i+1;
  82.             break;
  83.         }
  84.     cout <<"Resp=" << res << endl;
  85.     return res;
  86. }
  87.  
  88. int n;
  89. ll getAns(ll fill, ll cur, ll target) {
  90.     vector<int> q;
  91.     cout << "? ";
  92.     FOR(i, 1, n + 1) {
  93.         if (i == target) {cout << cur << " "; q.push_back(cur);}
  94.         else {cout << fill << " "; q.push_back(fill);}
  95.     }
  96.     cout << endl;
  97.     cout.flush();
  98.     ll ans;
  99.     ans = autoGetAns(q);
  100.     return ans;
  101. }
  102. void solve() {
  103.     cin >> n;
  104.     vi p(n, 0);
  105.     ll curR = n;
  106.     ll curL = 1;
  107.     ll lastFamous = 0;
  108.     ll done = 0;
  109.     ll flag = 0;
  110.     FOR(j, 1, n + 1) {
  111.         if (done == n) break;
  112.         if (done == n - 1) {
  113.             F0R(i, n) {
  114.                 if (p[i] == 0) {
  115.                     p[i] = curR;
  116.                     break;
  117.                 }
  118.                 done++;
  119.             }
  120.             break;
  121.         }
  122.         if (lastFamous && flag != curL) {
  123.             flag = curL;
  124.             ll ans = getAns(p[lastFamous - 1], curL, lastFamous);
  125.             if (ans < lastFamous && ans != 0) {
  126.                 p[ans - 1] = curL;
  127.                 curL++;
  128.                 done++;
  129.                 j--;
  130.                 continue;
  131.             }
  132.         }
  133.         ll ans = getAns(curL, curR, j);
  134.         if (ans == j) {
  135.             p[j - 1] = curL;
  136.             curL++;
  137.             lastFamous = j;
  138.             done++;
  139.         }
  140.         else if (ans != 0) {
  141.             p[ans - 1] = curR;
  142.             p[j - 1] = curL;
  143.             curL++;
  144.             curR--;
  145.             lastFamous = j;
  146.             done += 2;
  147.         }
  148.     }
  149.     while (done < n) {
  150.         ll ans = getAns(p[lastFamous - 1], curL, lastFamous);
  151.         if (ans < lastFamous && ans != 0) {
  152.             p[ans - 1] = curL;
  153.             curL++;
  154.             done++;
  155.             continue;
  156.         }
  157.     }
  158.     cout << "! ";
  159.     print(p);
  160.     cout << endl;
  161.     cout.flush();
  162. }
RAW Paste Data