1838F - Stuck Conveyor - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ff first
#define ss second
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
#define bint __int128

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

vector<vector<int>> sn1, sn2;
vector<pii> p1, p2;
vector<char> dir{'<', 'v', '>', '^'};
int n;
int q = 25;

#ifdef DEBUG

pii operator+(pii a, pii b) {
    return {a.ff + b.ff, a.ss + b.ss};
}

int row, col;
int d;
vector<pii> to{
        {0, -1},
        {1, 0},
        {0, 1},
        {-1, 0}
};
void gen() {
    row = 3;
    col = 7;
    d = 2;
}

bool ok(pii a) {
    return (0 <= a.ff && a.ff < n) && (0 <= a.ss && a.ss < n);
}

pii ask(pii a, int t) {
    q--;
    assert(q >= 0);
    cout << "? " << a.ff + 1 << ' ' << a.ss + 1 << '\n';
    if (t == 2) {
        for (auto &i : sn2) {
            for (auto j : i)
                cout << dir[j];
            cout << '\n';
        }
    } else {
        for (auto &i : sn1) {
            for (auto j : i)
                cout << dir[j];
            cout << '\n';
        }
    }
    cout.flush();
    pii ans = a;
    set<pii> used;
    while (ok(ans) && used.find(ans) == used.end()) {
        used.insert(ans);
        if (ans == mp(row - 1, col - 1)) {
            ans = ans + to[d];
            continue;
        }
        if (t == 1)
            ans = ans + to[sn1[ans.ff][ans.ss]];
        else
            ans = ans + to[sn2[ans.ff][ans.ss]];
    }
//    cin >> ans.ff >> ans.ss;
//    ans.ff--;
//    ans.ss--;
    if (ok(ans))
        ans = {-1, -1};
    cout << "ANS " << ans.ff + 1 << ' ' << ans.ss + 1 << '\n';
    return ans;
}
#else
pii ask(pii a, int t) {
    q--;
    assert(q >= 0);
    cout << "? " << a.ff + 1 << ' ' << a.ss + 1 << '\n';
    if (t == 2) {
        for (auto &i : sn2) {
            for (auto j : i)
                cout << dir[j];
            cout << '\n';
        }
    } else {
        for (auto &i : sn1) {
            for (auto j : i)
                cout << dir[j];
            cout << '\n';
        }
    }
    cout.flush();
    pii ans;
    cin >> ans.ff >> ans.ss;
    ans.ff--;
    ans.ss--;
    return ans;
}
#endif

inline void solve() {
    cin >> n;
    sn1.resize(n, vector<int>(n));
    sn2.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        if (i % 2) {
            for (int j = n - 1; j > 0; j--) {
                p1.pb({i, j});
                sn1[i][j] = 0;
            }
            p1.pb({i, 0});
            sn1[i][0] = 1;
        } else {
            for (int j = 0; j < n - 1; j++){
                p1.pb({i, j});
                sn1[i][j] = 2;
            }
            p1.pb({i, n - 1});
            sn1[i][n - 1] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i % 2) {
            p2.pb({i, n - 1});
            sn2[i][n - 1] = 3;
            for (int j = n - 2; j > -1; j--) {
                p2.pb({i, j});
                sn2[i][j] = 2;
            }
        } else {
            p2.pb({i, 0});
            sn2[i][0] = 3;
            for (int j = 1; j < n; j++) {
                p2.pb({i, j});
                sn2[i][j] = 0;
            }
        }
    }
    reverse(all(p2));
    pii st1, st2;
    st1 = {0, 0};
    if (n % 2)
        st2 = {n - 1, n - 1};
    else
        st2 = {n - 1, 0};
    pii fn1, fn2;
    if (n % 2)
        fn1 = {n, n - 1};
    else
        fn1 = {n, 0};
    fn2 = {-1, 0};
    pii a1, a2;
    a1 = ask(st1, 1);
    a2 = ask(st2, 2);
    if (a2 != fn2) {
        swap(p1, p2);
        swap(sn1, sn2);
        swap(st1, st2);
        swap(fn1, fn2);
    }
    int l = 0, r = p1.size();
    while (r - l > 1) {
        int m = (r + l) / 2;
        pii st = p1[m];
        pii a = ask(st, 1);
        if (a == fn1)
            r = m;
        else
            l = m;
    }
    pii a = p1[l];
    for (int i = 0; i < n; i++) {
        if (i < a.ff)
            sn1[i][a.ss] = 3;
        else
            sn1[i][a.ss] = 1;
    }
    for (int j = 0; j < n; j++) {
        if (j < a.ss)
            sn1[a.ff][j] = 0;
        else
            sn1[a.ff][j] = 2;
    }
    pii b = a;
    a = ask(a, 1);
    cout << "! " << b.ff + 1 << ' ' << b.ss + 1 << ' ';
    if (a.ff == -1)
        cout << '^';
    if (a.ff == n)
        cout << 'v';
    if (a.ss == -1)
        cout << '<';
    if (a.ss == n)
        cout << '>';
    cout.flush();
}

signed main() {
#ifndef DEBUG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif
    int tt = 1;
#ifdef DEBUG
    std::cin >> tt;
#endif
    while (tt--) {
#ifdef DEBUG
        gen();
        std::cout << "Test case#\n";
#endif
        solve();
    }
    return 0;
}