QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259500 | #5077. Card Game | NYCU_CartesianTree# | TL | 0ms | 0kb | C++20 | 4.3kb | 2023-11-20 23:39:38 | 2023-11-20 23:39:39 |
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