QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259500#5077. Card GameNYCU_CartesianTree#TL 0ms0kbC++204.3kb2023-11-20 23:39:382023-11-20 23:39:39

Judging History

你现在查看的是最新测评结果

  • [2023-11-20 23:39:39]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-11-20 23:39:38]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define F first 
#define S second 

vector<vector<int>>now(26,vector<int>(26));
map<vector<vector<int>>,int>ha;
    int n,m;
    
int bre(vector<vector<int>>);

int has(vector<vector<int>>haha){


    set<int>all;
    for(int i=0;i<haha.size();i++){
        int sz=haha[i].size();
        for(int j=0;j<sz;j++){
            if(haha[i][j]){
                vector<vector<int>>nn=haha;
                if(haha[i][j]==1){
                    int i1=i-1,i2=j-1;
                    while(i1>=0&&i2>=0&&nn[i1][i2]) nn[i1][i2]=0,i1--,i2--;
                    i1=i+1,i2=i+1;
                    while(i1<n&&i2<m&&nn[i1][i2]) nn[i1][i2]=0,i1++,i2++;
                    nn[i][j]=0;
                    all.insert(bre(nn));
                }
                else if(haha[i][j]==2){
                    int i1=i-1,i2=j-1;
                    while(i1>=0&&i2>=0&&nn[i1][i2]) nn[i1][i2]=0,i1--,i2--;
                    i1=i+1,i2=i+1;
                    while(i1<n&&i2<m&&nn[i1][i2]) nn[i1][i2]=0,i1++,i2++;
                    nn[i][j]=0;

                    i1=i-1,i2=j+1;
                    while(i1>=0&&i2<m&&nn[i1][i2]) nn[i1][i2]=0,i1--,i2++;
                    i1=i+1,i2=j-1;
                    while(i1<n&&i2>=0&&nn[i1][i2]) nn[i1][i2]=0,i1++,i2--;
                    
                    int t=has(nn);

                    // for(int ii=0;ii<n;ii++) {for(int jj=0;jj<m;jj++) cerr<<nn[ii][jj]<<" ";cerr<<"\n";}
                    
                    all.insert(t);
                }
                else{
                    int i1=i-1,i2=j+1;
                    while(i1>=0&&i2<m&&nn[i1][i2]) nn[i1][i2]=0,i1--,i2++;
                    i1=i+1,i2=j-1;
                    while(i1<n&&i2>=0&&nn[i1][i2]) nn[i1][i2]=0,i1++,i2--;
                    nn[i][j]=0;
                    all.insert(bre(nn));
                }
            }
        }
    }
    int ans=0;
    while(all.count(ans)) ans++;
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++) cerr<<haha[i][j]<<" ";cerr<<"\n";
    // }
    // cerr<<ans<<"\n";]=
    return ans;
}

int fx[]={1,1,-1,-1},fy[]={1,-1,1,-1};
int vis[26][26];
int bre(vector<vector<int>>tt){
    int xo=0;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) vis[i][j]=0;

    vector<tuple<int,int,int>>iu1;
    int iu2=27,iu3=27;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(tt[i][j]) iu2=min(iu2,i),iu3=min(iu3,j),iu1.pb({i,j,tt[i][j]});
        }
    }
    vector<vector<int>>gg(26,vector<int>(26,0));
    for(auto [t1,t2,t3]:iu1){
        t1-=iu2,t2-=iu3;
        gg[t1][t2]=t3;
    }
    if(ha.count(gg)) return ha[gg];

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(tt[i][j]){
                queue<pair<int,int>>hh;
                vector<tuple<int,int,int>>tot;
                hh.push({i,j});
                int x1=50,y1=50;
                while(hh.size()){
                    auto t=hh.front();hh.pop();
                    tot.pb({t.F,t.S,tt[t.F][t.S]});
                    x1=min(x1,t.F);
                    y1=min(y1,t.S);
                    for(int jj=0;jj<4;jj++){
                        int xx=t.F+fx[jj],yy=t.S+fy[jj];
                        if(0<=xx&&xx<n&&0<=yy&&yy<m&&!vis[xx][yy]&&tt[xx][yy]){
                            vis[xx][yy]=1;
                            hh.push({xx,yy});
                        }
                    }
                }
                vector<vector<int>>iu(26,vector<int>(26,0));
                for(auto [b1,b2,b3]:tot){
                    b1-=x1,b2-=y1;
                    iu[b1][b2]=b3;
                }
                
                if(ha.count(iu)) xo^=ha[iu];
                else ha[iu]=bre(iu),xo^=ha[iu]; 
            }
        }
    }
    ha[gg]=xo;
    return xo;
}

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char t;
            cin>>t;
            int h;
            if(t=='B') h=1;
            else if(t=='G') h=2;
            else h=3;
            now[i][j]=h;
        }
    }

    if(has(now)) cout<<"W";
    else cout<<"L";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1 3
BBB


output:


result: