#1157356 (C++23) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: yuunegi
• 提出日時: 2026-04-14 23:17:38
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 58 ms / 2,000 ms
• コード長: 3,175 bytes
• コンパイル時間: 2,688 ms
• コンパイル使用メモリ: 344,776 KB
• 実行使用メモリ: 30,064 KB
• スコア: 159
• 平均クエリ数: 36.62
• 最終ジャッジ日時: 2026-04-14 23:54:54
• 合計ジャッジ時間: 5,152 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
other	AC * 16

ソースコード

#include <bits/stdc++.h>
using namespace std;
int main(void){
    int id,n,m;
    cin>>id>>n>>m;
    long long a[n];
    vector<int> k(m+1,0);//各カードの枚数
    for(int i=0;i<n;i++){
        cin>>a[i];
        k[a[i]]++;
    }
    //別圧縮?
    long long kai=1,rui=1;
    for(int i=1;i<=m;i++)kai*=i;
    for(int i=0;i<n;i++)rui*=m;
    int flag2=(kai<rui);
    
    long long as1=0;//圧縮する
    long long asmax=0;
    for(long long i=m;i>0;i--){
        as1*=i+1;
        as1+=k[i];
        asmax*=i+1;
        asmax+=i;
    }
    vector<long long>send;//m進数変換
    while(asmax){
        send.push_back(as1%m);
        as1/=m;
        asmax/=m;
    }
    reverse(send.begin(),send.end());
    vector<int>ba(m+1,0);//場にあるカードの枚数
    vector<int>isask(m+1,0);//尋ねたか
    long long as2=0,as3=0;//相手の圧縮列
    int it=0,flag=0,myask=0;
    int ss=0;//総質問回数
    
    vector<int>opk(m+1,0);//相手のカード列
    while(1){
        string s;
        cin>>s;
        if(s=="TURN"){
            if(flag==0){
                if(flag2){
                    cout<<"ASK "<<send[it]+1<<endl;
                }else{
                    cout<<"ASK "<<a[it]<<endl;
                }
                it++;
                myask=1;
            }
            if(flag==2){
                int sum=0;
                for(int i=1;i<=m;i++){
                    sum+=max(ba[i],k[i]+opk[i]);
                }
                if(sum==3*n){
                    flag=3;
                }else{
                    for(int i=m;i>=1;i--){
                        if(isask[i]==0){
                            cout<<"ASK "<<i<<endl;
                            break;
                        }
                    }
                }
            }
            if(flag==3){
                int sum2=0;
                cout<<"GUESS ";
                for(int i=1;i<=m;i++){
                    if(ba[i]-k[i]-opk[i]>0){
                        cout<<i<<(sum2==n-1?"":" ");
                        ba[i]--;
                        sum2++;
                        i--;
                    }
                }
                cout<<endl;
                flag=4;
            }
        }else if(s=="WAIT"){
            continue;
        }else if(s=="COUNT"){
            int x,k2;
            cin>>x>>k2;
            if(flag==0&&myask==0&&flag2){
                as2*=m;
                as2+=(x-1);
            }else if(flag==0&&myask==0&&flag2==0){
                opk[x]++;
            }
            myask=0;
            if(isask[x]==0){
                ba[x]=k2;
                isask[x]=1;
            }
            ss++;
            if(ss==send.size()*2&&flag2)flag=1;
            if(ss==n*2&&flag2==0)flag=1;
        }else if(s=="GUESSED"){
            int gm;
            cin>>gm>>gm;
        }else if(s=="END"){
            break;
        }else{
            return 1;
        }
        if(flag==1&&flag2){
            for(long long i=1;i<=m;i++){
                opk[i]=as2%(i+1);
                as2/=(i+1);
            }
            flag=2;
        }else if(flag==1&&flag2==0){
            flag=2;
        }
    }
    return 0;
}