結果

問題 No.3395 Range Flipping Game
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 15:25:53
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 2,404 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,030 ms
コンパイル使用メモリ 282,060 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-12 15:26:00
合計ジャッジ時間 6,241 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:11:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |     scanf("%lld",&t);
      |     ~~~~~^~~~~~~~~~~
main.cpp:13:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |         scanf("%lld",&n);
      |         ~~~~~^~~~~~~~~~~
main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=250005;
char s[maxn+5];
bool v1[15],v2[15],h[5];
vector<ll> st,cur,nx;
int main(){
    ll t,n,i,j,k,ans,p,f,nf,np,ch,mn;
    bool fd;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        scanf("%s",s+1);
        for(i=0;i<12;i++) v1[i]=0;
        v1[0]=1,ans=-1;
        for(i=1;i<=n;i++){
            for(j=0;j<12;j++) v2[j]=0;
            fd=0,st.clear();
            for(j=0;j<12;j++){
                if(not v1[j]) continue;
                p=j/3,f=j%3;
                for(nf=f;nf<=(f==1?2:(f==0?1:2));nf++){
                    if(f==2 and nf!=2) continue;
                    ch=(s[i]=='A'?0:1);
                    if(nf==1) ch^=1;
                    np=p;
                    if(p==0) np=(ch==1?1:2);
                    else if(p==1) np=(ch==1?1:2);
                    else if(p==2) np=(ch==0?2:3);
                    else if(p==3) np=(ch==1?3:4);
                    if(np==4) fd=1,st.push_back(nf);
                    else v2[np*3+nf]=1;
                }
            }
            if(fd){
                ans=i;
                break;
            }
            for(j=0;j<12;j++) v1[j]=v2[j];
        }
        if(ans==-1){
            for(i=1;i<=n;i++) printf("B");
            printf("\n");
        }
        else{
            for(i=1;i<ans;i++) printf("B");
            printf("A");
            cur=st;
            for(i=ans+1;i<=n;i++){
                mn=2;
                for(j=0;j<cur.size();j++){
                    f=cur[j];
                    for(nf=f;nf<=(f==1?2:(f==0?1:2));nf++){
                        if(f==2 and nf!=2) continue;
                        ch=(s[i]=='A'?0:1);
                        if(nf==1) ch^=1;
                        if(ch<mn) mn=ch;
                    }
                }
                printf("%c",mn==0?'A':'B');
                nx.clear(),h[0]=0,h[1]=0,h[2]=0;
                for(j=0;j<cur.size();j++){
                    f=cur[j];
                    for(nf=f;nf<=(f==1?2:(f==0?1:2));nf++){
                        if(f==2 and nf!=2) continue;
                        ch=(s[i]=='A'?0:1);
                        if(nf==1) ch^=1;
                        if(ch==mn and not h[nf]) h[nf]=1,nx.push_back(nf);
                    }
                }
                cur=nx;
            }
            printf("\n");
        }
    }
    return 0;
}
0