yukicoder No.282 おもりと天秤(2)

問題

No.282 おもりと天秤(2) - yukicoder

解法

奇偶転置ソートというアルゴリズムを利用します。
奇偶転置ソート - Wikipedia

bool cmp[505][505];
int C[505];
bool comp(int a, int b) {return cmp[a][b];}

int main() {
    int N;
    cin >> N;
    vector<int> ans(N);
    for (int i = 0; i < N; i++) ans[i] = i;
    for (int t = 0; t < 2*N; t++) {
        cout << "? ";
        if (t%2==0) {
            int cnt = 0;
            for (int i = 0; i+1 < N; i+=2) {
                cout << ans[i]+1 << " " << ans[i+1]+1 << " ";
                cnt++;
            }
            for (int i = cnt; i < N; i++) {
                cout << 0 << " " << 0;
                if (i < N-1) cout << " ";
            }
            cout << endl;
            cout.flush();
            for (int i = 0; i+1 < N; i+=2) {
                char c;
                cin >> c;
                if (c == '>') swap(ans[i], ans[i+1]);
            }
            for (int i = cnt; i < N; i++) {
                char c;
                cin >> c;
            }
        } else {
            int cnt = 0;
            for (int i = 1; i+1 < N; i+=2) {
                cout << ans[i]+1 << " " << ans[i+1]+1 << " ";
                cnt++;
            }
            for (int i = cnt; i < N; i++) {
                cout << 0 << " " << 0;
                if (i < N-1) cout << " ";
            }
            cout << endl;
            cout.flush();
            for (int i = 1; i+1 < N; i+=2) {
                char c;
                cin >> c;
                if (c == '>') swap(ans[i], ans[i+1]);
            }
            for (int i = cnt; i < N; i++) {
                char c;
                cin >> c;
            }
        }
    }
    cout << "! ";
    for (int i = 0; i < N; i++) {
        cout << ans[i]+1;
        if (i < N-1) cout << " ";
    }
    cout << endl;
    cout.flush();
    return 0;
}