結果

問題 No.2577 Simple Permutation Guess
ユーザー tko919
提出日時 2023-12-05 01:08:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 357 ms / 2,000 ms
コード長 3,122 bytes
コンパイル時間 2,370 ms
コンパイル使用メモリ 202,996 KB
最終ジャッジ日時 2025-02-18 07:35:36
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 111
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) lower_bound(ALL(v),(x))-(v).begin()
#define UB(v,x) upper_bound(ALL(v),(x))-(v).begin()

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "sol.cpp"

int ask(vector<int>& a){
    cout<<"? ";
    rep(i,0,a.size())cout<<a[i]+1<<' ';
    cout<<endl;
    int B;
    cin>>B;
    return B;
}

void answer(vector<int>& a){
    cout<<"! ";
    rep(i,0,a.size())cout<<a[i]+1<<' ';
    cout<<endl;
}

int main(){
    int n;
    cin>>n;

    vector<int> L(n),R(n);
    iota(ALL(L),0);
    R=L;
    reverse(ALL(R));
    auto last=R;

    auto convert=[&](vector<int>& a)->vector<int>{
        vector<int> cnt(n),ret(n);
        rep(i,0,n){
            int sum=0;
            rep(j,0,a[i])sum+=cnt[j];
            ret[n-i-1]=a[i]-sum;
            cnt[a[i]]++;
        }
        return ret;
    };

    auto inverse=[&](vector<int>& a)->vector<int>{
        vector<int> ret(n),cnt(n);
        for(int i=n-1;i>=0;i--){
            int sum=0;
            rep(j,0,n)if(cnt[j]==0){
                sum++;
                if(sum==a[i]+1){
                    ret[n-1-i]=j;
                    break;
                }
            }
            cnt[ret[n-1-i]]++;
        }
        return ret;
    };

    for(;;){
        auto nxt=L;
        next_permutation(ALL(nxt));
        if(nxt==R)break;

        auto cL=convert(L);
        auto cR=convert(R);

        vector<int> cmid(n),odd(n),add(n);
        for(int i=n-1;i>=0;i--){
            cmid[i]=(cL[i]+cR[i])/2;
            odd[i]=(cL[i]+cR[i])&1;
        }
        for(int i=n-1;i>0;i--)if(odd[i]){
            if(i&1){
                if(i>1)add[i-2]+=i*(i-1)/2;
                else add[1]++;
            }
            else{
                add[i-1]+=i/2;
            }
        }
        int up=0;
        rep(i,0,n){
            cmid[i]+=add[i]+up;
            up=0;
            if(cmid[i]>i){
                up+=cmid[i]/(i+1);
                cmid[i]%=(i+1);
            }
        }
        assert(up==0);
        auto mid=inverse(cmid);
        
        if(ask(mid))L=mid;
        else R=mid;
    }
    if(R==last and ask(R))answer(R);
    else answer(L);
    return 0;
}
0