#938623 (C++17) No.2577 Simple Permutation Guess

提出ソース

結果

問題	No.2577 Simple Permutation Guess
ユーザー	👑 potato167
提出日時	2023-12-16 04:27:11
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	199 ms / 2,000 ms
コード長	2,922 bytes
コンパイル時間	2,347 ms
コンパイル使用メモリ	210,224 KB
実行使用メモリ	24,012 KB
平均クエリ数	248.84
最終ジャッジ日時	2023-12-16 04:27:30
合計ジャッジ時間	18,980 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	28 ms 24,000 KB
testcase_01	AC	150 ms 24,000 KB
testcase_02	AC	48 ms 24,000 KB
testcase_03	AC	24 ms 24,000 KB
testcase_04	AC	65 ms 24,000 KB
testcase_05	AC	75 ms 24,000 KB
testcase_06	AC	191 ms 24,000 KB
testcase_07	AC	191 ms 24,000 KB
testcase_08	AC	194 ms 24,000 KB
testcase_09	AC	199 ms 24,000 KB
testcase_10	AC	191 ms 24,000 KB
testcase_11	AC	24 ms 24,000 KB
testcase_12	AC	24 ms 24,000 KB
testcase_13	AC	26 ms 24,000 KB
testcase_14	AC	25 ms 24,000 KB
testcase_15	AC	25 ms 24,000 KB
testcase_16	AC	24 ms 24,000 KB
testcase_17	AC	23 ms 24,000 KB
testcase_18	AC	23 ms 24,000 KB
testcase_19	AC	23 ms 24,000 KB
testcase_20	AC	25 ms 24,000 KB
testcase_21	AC	22 ms 24,000 KB
testcase_22	AC	24 ms 24,012 KB
testcase_23	AC	23 ms 24,012 KB
testcase_24	AC	25 ms 24,012 KB
testcase_25	AC	23 ms 24,012 KB
testcase_26	AC	22 ms 24,012 KB
testcase_27	AC	23 ms 24,012 KB
testcase_28	AC	23 ms 24,012 KB
testcase_29	AC	25 ms 24,012 KB
testcase_30	AC	24 ms 24,012 KB
testcase_31	AC	23 ms 24,000 KB
testcase_32	AC	23 ms 24,000 KB
testcase_33	AC	23 ms 24,000 KB
testcase_34	AC	23 ms 24,000 KB
testcase_35	AC	23 ms 24,000 KB
testcase_36	AC	23 ms 24,000 KB
testcase_37	AC	23 ms 24,000 KB
testcase_38	AC	23 ms 24,000 KB
testcase_39	AC	24 ms 24,000 KB
testcase_40	AC	24 ms 24,000 KB
testcase_41	AC	26 ms 24,000 KB
testcase_42	AC	25 ms 24,000 KB
testcase_43	AC	23 ms 24,000 KB
testcase_44	AC	24 ms 24,000 KB
testcase_45	AC	23 ms 24,000 KB
testcase_46	AC	22 ms 24,000 KB
testcase_47	AC	23 ms 24,000 KB
testcase_48	AC	23 ms 24,000 KB
testcase_49	AC	23 ms 24,000 KB
testcase_50	AC	23 ms 24,000 KB
testcase_51	AC	24 ms 24,000 KB
testcase_52	AC	23 ms 24,000 KB
testcase_53	AC	23 ms 24,000 KB
testcase_54	AC	23 ms 24,000 KB
testcase_55	AC	23 ms 24,000 KB
testcase_56	AC	23 ms 24,000 KB
testcase_57	AC	23 ms 24,000 KB
testcase_58	AC	23 ms 24,000 KB
testcase_59	AC	23 ms 24,000 KB
testcase_60	AC	23 ms 24,000 KB
testcase_61	AC	24 ms 24,000 KB
testcase_62	AC	23 ms 24,000 KB
testcase_63	AC	24 ms 24,000 KB
testcase_64	AC	24 ms 24,012 KB
testcase_65	AC	24 ms 24,012 KB
testcase_66	AC	23 ms 24,012 KB
testcase_67	AC	25 ms 24,012 KB
testcase_68	AC	23 ms 24,012 KB
testcase_69	AC	24 ms 24,012 KB
testcase_70	AC	26 ms 24,012 KB
testcase_71	AC	23 ms 24,012 KB
testcase_72	AC	24 ms 24,012 KB
testcase_73	AC	24 ms 24,000 KB
testcase_74	AC	27 ms 24,000 KB
testcase_75	AC	25 ms 24,000 KB
testcase_76	AC	25 ms 24,000 KB
testcase_77	AC	25 ms 24,000 KB
testcase_78	AC	28 ms 24,000 KB
testcase_79	AC	26 ms 24,000 KB
testcase_80	AC	27 ms 24,000 KB
testcase_81	AC	26 ms 24,000 KB
testcase_82	AC	24 ms 24,000 KB
testcase_83	AC	25 ms 24,000 KB
testcase_84	AC	26 ms 24,000 KB
testcase_85	AC	26 ms 24,000 KB
testcase_86	AC	26 ms 24,000 KB
testcase_87	AC	26 ms 24,012 KB
testcase_88	AC	26 ms 24,012 KB
testcase_89	AC	26 ms 24,012 KB
testcase_90	AC	27 ms 24,012 KB
testcase_91	AC	25 ms 24,012 KB
testcase_92	AC	162 ms 24,012 KB
testcase_93	AC	145 ms 24,012 KB
testcase_94	AC	131 ms 24,012 KB
testcase_95	AC	184 ms 24,012 KB
testcase_96	AC	184 ms 24,012 KB
testcase_97	AC	173 ms 24,012 KB
testcase_98	AC	170 ms 24,012 KB
testcase_99	AC	183 ms 24,012 KB
testcase_100	AC	141 ms 24,012 KB
testcase_101	AC	173 ms 24,012 KB
evil_1_rnd_1.txt	AC	384 ms 24,012 KB
evil_1_rnd_2.txt	AC	416 ms 24,012 KB
evil_2_big_1.txt	AC	509 ms 24,012 KB
evil_2_big_2.txt	AC	542 ms 24,012 KB
evil_2_big_3.txt	AC	511 ms 24,012 KB
evil_3_sorted_1.txt	AC	271 ms 24,012 KB
evil_4_sorted_rev_1.txt	AC	204 ms 24,012 KB
evil_4_sorted_rev_2.txt	AC	306 ms 24,012 KB
evil_400_sorted.txt	AC	513 ms 24,012 KB
evil_400_sorted_rev.txt	AC	520 ms 24,012 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
using ld=long double;
const ll ILL=2167167167167167167;
const int INF=2100000000;
const int mod=998244353;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
void yneos(bool a,bool upp=0){if(a) cout<<(upp?"YES\n":"Yes\n"); else cout<<(upp?"NO\n":"No\n");}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){assert(!a.empty());T ans=a[0]-a[0];for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}


void solve();
// oddloop
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t=1;
    //cin>>t;
    rep(i,0,t) solve();
}

void solve(){
    int N;
    cin>>N;
    vector<int> L(N),R(N);
    auto f=[&](vector<int> p) -> vector<int> {
        vector<int> res(N),seen(N);
        rep(i,0,N){
            int ind=0;
            int val=0;
            while(val<=p[i]){
                val+=1-seen[ind];
                ind++;
            }
            res[i]=ind;
            seen[ind-1]=1;
        }
        return res;
    };
    rep(i,0,N) R[i]=N-1-i;
    R[N-1]=1;
    while(true){
        vector<int> M(N);
        rep(i,0,N) M[i]=(L[i]+R[i]);
        rep(i,0,N){
            if((M[i]&1)!=0&&i!=N-1){
                M[i+1]+=(N-i-1);
            }
            M[i]/=2;
        }
        for(int i=N-1;i>0;i--){
            M[i-1]+=M[i]/(N-i);
            M[i]%=(N-i);
        }
        if(L==M||R==M) break;
        auto tmp=f(M);
        cout<<"?";
        rep(i,0,N) cout<<" "<<tmp[i];
        cout<<endl;
        int ret;cin>>ret;
        if(ret) L=M;
        else R=M;
    }
    cout<<"!";
    auto tmp=f(L);
    rep(i,0,N) cout<<" "<<tmp[i];
    cout<<endl;
}

yukicoder

結果

テストケース

ソースコード