Advertisement
Kambarych

Im noob

Jan 5th, 2025
69
0
5 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define For(i, n)           for(int i = 0; i < n; ++i)
  6. #define all(x)              (x).begin(),(x).end()
  7. #define rall(x)             (x).rbegin(),(x).rend()
  8. #define ls(x)               x+x+1
  9. #define rs(x)               x+x+2
  10.  
  11. #define ld                  long double
  12. #define pii                 pair<int, int>
  13. #define vt                  vector
  14. #define ll                  long long
  15.  
  16. #define sim template < class c
  17. #define ris return * this
  18. #define dor > debug & operator <<
  19. #define eni(x) sim > typename \
  20. enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  21. sim > struct rge { c b, e; };
  22. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  23. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  24. sim > char dud(...);
  25. #define LOCAL
  26. struct debug {
  27. #ifdef LOCAL
  28. ~debug() { cerr << endl; }
  29. eni(!=) cerr << boolalpha << i; ris; }
  30. eni(==) ris << range(begin(i), end(i)); }
  31. sim, class b dor(pair < b, c > d) {
  32. ris << "(" << d.first << ", " << d.second << ")";
  33. }
  34. sim dor(rge<c> d) {
  35. *this << "[";
  36. for (auto it = d.b; it != d.e; ++it)
  37.     *this << ", " + 2 * (it == d.b) << *it;
  38. ris << "]";
  39. }
  40. #else
  41. sim dor(const c&) { ris; }
  42. #endif
  43. };
  44. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  45.  
  46. template<typename T> void read(vt<T> & a) {For(i, a.size()) cin >> a[i];}
  47. template<typename T> void read2(vt<vt<T> > & a) {For(i, a.size()) read(a[i]);}
  48. template<typename T> void print(vt<T> & a) {For(i, a.size()) cout << a[i] << " "; cout << endl;}
  49. template<typename T> void print2(vt<vt<T> > & a) {For(i, a.size()) print(a[i]);}
  50.  
  51. const int MAX = 1e9;
  52. const int MOD = 1000000007;
  53. const ll  INF = 1e18;
  54. const ld  PI  = 3.14159265358979323846;
  55.  
  56. const int ALPH = 26;
  57.  
  58. string ask(vt<char> s) {
  59.     cout << "? " << string(s.begin(), s.end()) << endl;
  60.     string r; cin >> r;
  61.     return r;
  62. }
  63.  
  64. void solve() {
  65.     int n; cin >> n;
  66.     vt<char> s(n);
  67.     for (int i = 0; i < n; i++) {
  68.         s[i] = ('a' + (i % ALPH));
  69.     }
  70.     string r = ask(s);
  71.     map<char, deque<int>> positions;
  72.     for (int i = 0; i < n; i++) {
  73.         positions[r[i]].push_back(i);
  74.     }
  75.     map<string, vt<int>> dp_p;
  76.     map<string, vt<int>> dp_s;
  77.     for (int i = 0; i < n; i++) {
  78.         dp_p[string() + s[i]].push_back(positions[s[i]].front());
  79.         dp_s[string() + s[i]].push_back(i);
  80.         positions[s[i]].pop_front();
  81.     }
  82.     vt<string> keys;
  83.     for (int i = 0; i < n; i++) {
  84.         keys.push_back(string() + s[i]);
  85.     }
  86.     for (int it = 0; it < 3; it++) {
  87.         for (auto [str, s_idxs] : dp_s) {
  88.             for (int i = 0; i < s_idxs.size(); i++) {
  89.                 s[s_idxs[i]] = ('a' + (i % ALPH));
  90.             }
  91.         }
  92.         string r = ask(s);
  93.         for (int i = 0; i < n; i++) {
  94.             keys[i] += s[i];
  95.         }
  96.         map<string, vt<int>> new_dp_p;
  97.         map<string, vt<int>> new_dp_s;
  98.         for (auto [str, p_idxs] : dp_p) {
  99.             map<char, deque<int>> positions;
  100.             for (int i = 0; i < p_idxs.size(); i++) {
  101.                 positions[r[p_idxs[i]]].push_back(p_idxs[i]);
  102.             }
  103.             auto s_idxs = dp_s[str];
  104.             for (int i = 0; i < s_idxs.size(); i++) {
  105.                 new_dp_p[str + s[s_idxs[i]]].push_back(positions[s[s_idxs[i]]].front());
  106.                 new_dp_s[str + s[s_idxs[i]]].push_back(s_idxs[i]);
  107.                 positions[s[s_idxs[i]]].pop_front();
  108.             }
  109.         }
  110.         dp_p = new_dp_p;
  111.         dp_s = new_dp_s;
  112.     }
  113.     vt<pair<string, int> > kvs;
  114.     assert(dp_p.size() == n);
  115.     for (auto [str, idxs] : dp_p) {
  116.         kvs.emplace_back(str, idxs[0]);
  117.     }
  118.     map<string, int> order;
  119.     for (int i = 0; i < n; i++) {
  120.         order[keys[i]] = i;
  121.     }
  122.     sort(all(kvs), [&] (pair<string, int> lhs, pair<string, int> rhs) -> bool {
  123.         return order[lhs.first] < order[rhs.first];
  124.     });
  125.     cout << "!";
  126.     For(i, n) {
  127.         cout << " " << kvs[i].second + 1;
  128.     }
  129.     cout << endl;
  130. }
  131.  
  132. // THE SOLUTION IS ALWAYS SIMPLE
  133. // THE CODE IS ALWAYS SHORT
  134.  
  135. int main() {
  136.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  137. #ifdef DEBUG
  138.     freopen("output.txt", "w", stdout);
  139.     freopen("input.txt", "r", stdin);
  140. #endif
  141.     int T = 1;
  142.     For(t, T) solve();
  143.     return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement