Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define For(i, n) for(int i = 0; i < n; ++i)
- #define all(x) (x).begin(),(x).end()
- #define rall(x) (x).rbegin(),(x).rend()
- #define ls(x) x+x+1
- #define rs(x) x+x+2
- #define ld long double
- #define pii pair<int, int>
- #define vt vector
- #define ll long long
- #define sim template < class c
- #define ris return * this
- #define dor > debug & operator <<
- #define eni(x) sim > typename \
- enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
- sim > struct rge { c b, e; };
- sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
- sim > auto dud(c* x) -> decltype(cerr << *x, 0);
- sim > char dud(...);
- #define LOCAL
- struct debug {
- #ifdef LOCAL
- ~debug() { cerr << endl; }
- eni(!=) cerr << boolalpha << i; ris; }
- eni(==) ris << range(begin(i), end(i)); }
- sim, class b dor(pair < b, c > d) {
- ris << "(" << d.first << ", " << d.second << ")";
- }
- sim dor(rge<c> d) {
- *this << "[";
- for (auto it = d.b; it != d.e; ++it)
- *this << ", " + 2 * (it == d.b) << *it;
- ris << "]";
- }
- #else
- sim dor(const c&) { ris; }
- #endif
- };
- #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- template<typename T> void read(vt<T> & a) {For(i, a.size()) cin >> a[i];}
- template<typename T> void read2(vt<vt<T> > & a) {For(i, a.size()) read(a[i]);}
- template<typename T> void print(vt<T> & a) {For(i, a.size()) cout << a[i] << " "; cout << endl;}
- template<typename T> void print2(vt<vt<T> > & a) {For(i, a.size()) print(a[i]);}
- const int MAX = 1e9;
- const int MOD = 1000000007;
- const ll INF = 1e18;
- const ld PI = 3.14159265358979323846;
- const int ALPH = 26;
- string ask(vt<char> s) {
- cout << "? " << string(s.begin(), s.end()) << endl;
- string r; cin >> r;
- return r;
- }
- void solve() {
- int n; cin >> n;
- vt<char> s(n);
- for (int i = 0; i < n; i++) {
- s[i] = ('a' + (i % ALPH));
- }
- string r = ask(s);
- map<char, deque<int>> positions;
- for (int i = 0; i < n; i++) {
- positions[r[i]].push_back(i);
- }
- map<string, vt<int>> dp_p;
- map<string, vt<int>> dp_s;
- for (int i = 0; i < n; i++) {
- dp_p[string() + s[i]].push_back(positions[s[i]].front());
- dp_s[string() + s[i]].push_back(i);
- positions[s[i]].pop_front();
- }
- vt<string> keys;
- for (int i = 0; i < n; i++) {
- keys.push_back(string() + s[i]);
- }
- for (int it = 0; it < 3; it++) {
- for (auto [str, s_idxs] : dp_s) {
- for (int i = 0; i < s_idxs.size(); i++) {
- s[s_idxs[i]] = ('a' + (i % ALPH));
- }
- }
- string r = ask(s);
- for (int i = 0; i < n; i++) {
- keys[i] += s[i];
- }
- map<string, vt<int>> new_dp_p;
- map<string, vt<int>> new_dp_s;
- for (auto [str, p_idxs] : dp_p) {
- map<char, deque<int>> positions;
- for (int i = 0; i < p_idxs.size(); i++) {
- positions[r[p_idxs[i]]].push_back(p_idxs[i]);
- }
- auto s_idxs = dp_s[str];
- for (int i = 0; i < s_idxs.size(); i++) {
- new_dp_p[str + s[s_idxs[i]]].push_back(positions[s[s_idxs[i]]].front());
- new_dp_s[str + s[s_idxs[i]]].push_back(s_idxs[i]);
- positions[s[s_idxs[i]]].pop_front();
- }
- }
- dp_p = new_dp_p;
- dp_s = new_dp_s;
- }
- vt<pair<string, int> > kvs;
- assert(dp_p.size() == n);
- for (auto [str, idxs] : dp_p) {
- kvs.emplace_back(str, idxs[0]);
- }
- map<string, int> order;
- for (int i = 0; i < n; i++) {
- order[keys[i]] = i;
- }
- sort(all(kvs), [&] (pair<string, int> lhs, pair<string, int> rhs) -> bool {
- return order[lhs.first] < order[rhs.first];
- });
- cout << "!";
- For(i, n) {
- cout << " " << kvs[i].second + 1;
- }
- cout << endl;
- }
- // THE SOLUTION IS ALWAYS SIMPLE
- // THE CODE IS ALWAYS SHORT
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifdef DEBUG
- freopen("output.txt", "w", stdout);
- freopen("input.txt", "r", stdin);
- #endif
- int T = 1;
- For(t, T) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement