QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259504 | #5077. Card Game | NYCU_CartesianTree# | TL | 40ms | 10396kb | C++20 | 4.4kb | 2023-11-20 23:42:55 | 2023-11-20 23:42:56 |
Judging History
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