結果

問題 No.3592 I Love LIS
コンテスト
ユーザー GOTKAKO
提出日時 2026-07-18 11:20:24
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,967 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,242 ms
コンパイル使用メモリ 223,640 KB
実行使用メモリ 9,420 KB
平均クエリ数 4484.22
最終ジャッジ日時 2026-07-18 11:20:50
合計ジャッジ時間 23,753 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

random_device rnd;
mt19937 mt(rnd());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    int query = 12000;
    auto ask = [&](vector<int> A) -> int {
        query--;
        assert(query >= 0);
        cout << "?";
        for(auto a : A) cout << " " << a; cout << endl;
        int ret; cin >> ret;
        if(ret == -1) exit(0);
        return ret;
    };
    auto ans = [&](vector<int> P) -> void {
        cout << "!";
        for(auto a : P) cout << " " << a+1; cout << endl;
        exit(0);
    };

    auto check = [&](vector<int> &A,int L,int M,int R) -> vector<int> {
        vector<int> ret;
        int pos = L,pos2 = M;
        while(pos != M && pos2 != R){
            vector<int> B(N,2);
            int p1 = A.at(pos),p2 = A.at(pos2);
            B.at(p1) = 0,B.at(p2) = 1;
            if(ask(B) == 3) ret.push_back(p1),pos++;
            else ret.push_back(p2),pos2++;
        }
        while(pos != M) ret.push_back(A.at(pos++));
        while(pos2 != R) ret.push_back(A.at(pos2++));
        return ret;
    };
    auto merge = [&](auto merge,vector<int> &A,int L = -1,int R = -1) -> void {
        if(L == -1 && R == -1) L = 0,R = A.size();
        if(R-L <= 1) return;
        int M = (L+R)/2;
        merge(merge,A,L,M); merge(merge,A,M,R);
        vector<int> Ls,Rs;
        for(int i=L; i<M; i++) Ls.push_back(A.at(i));
        for(int i=M; i<R; i++) Rs.push_back(A.at(i));
        
        auto C = check(A,L,M,R);
        for(int i=L; i<R; i++) A.at(i) = C.at(i-L);
    };

    vector<int> P(N),X(N,1);
    for(int i=0; i<N; i++) P.at(i) = i;
    shuffle(P.begin(),P.end(),mt);
    for(int i=0; i<N; i++){
        X.at(P.at(i)) = 0;
        if(ask(X) == 1){swap(P.at(i),P.back()); break;}
        X.at(P.at(i)) = 1;
    }

    merge(merge,P,0,N-1);
    vector<int> answer(N);
    for(int i=0; i<N; i++) answer.at(P.at(i)) = i;
    ans(answer);
}
0