QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259504#5077. Card GameNYCU_CartesianTree#TL 40ms10396kbC++204.4kb2023-11-20 23:42:552023-11-20 23:42:56

Judging History

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

  • [2023-11-20 23:42:56]
  • 评测
  • 测评结果:TL
  • 用时:40ms
  • 内存:10396kb
  • [2023-11-20 23:42:55]
  • 提交

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){
    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(haha[i][j]) iu2=min(iu2,i),iu3=min(iu3,j),iu1.pb({i,j,haha[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];
    haha=gg;

    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(has(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(has(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";]=
    ha[haha]=ans;
    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;



//     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: 100
Accepted
time: 1ms
memory: 3920kb

input:

1 3
BBB


output:

W

result:

ok single line: 'W'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

2 3
BBG
RGR


output:

W

result:

ok single line: 'W'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

2 2
GG
GG


output:

L

result:

ok single line: 'L'

Test #4:

score: 0
Accepted
time: 15ms
memory: 7188kb

input:

1 10
RRRRRRRRRR

output:

L

result:

ok single line: 'L'

Test #5:

score: 0
Accepted
time: 27ms
memory: 10208kb

input:

1 11
BBBBBBBBBBB

output:

W

result:

ok single line: 'W'

Test #6:

score: 0
Accepted
time: 18ms
memory: 6848kb

input:

10 1
G
G
G
G
G
G
G
G
G
G

output:

L

result:

ok single line: 'L'

Test #7:

score: 0
Accepted
time: 40ms
memory: 10396kb

input:

11 1
R
R
R
R
R
R
R
R
R
R
R

output:

W

result:

ok single line: 'W'

Test #8:

score: -100
Time Limit Exceeded

input:

2 20
BBGGBGBGGBBGGBGGBGGG
GGBBBGBGBBBGBGGGGGGG

output:


result: