Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
28950 LYLAKIOI 【BJ】T1 C++ 运行超时 0 1000 MS 296 KB 4715 2024-05-01 09:31:00

Tests(8/13):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=1e6+10; const string ss=" ZSJLTOI"; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; int n,m,T[10],used[maxn]; bool vis[maxn]; int NEED; int g(int x,int y){ return (x-1)*m+y; } struct diff { int x,y; diff(int _x,int _y){ x=_x,y=_y; }diff(){} }; bool operator<(diff a,diff b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } struct _ { diff A[4][4]; int LIM; _(){} void rev(int x){ vector<diff>g; up(i,0,3)g.p_b(diff(A[x][i].y,-A[x][i].x)); sort(g.begin(),g.end()); int mnx=1e9,mny=1e9; for(auto it:g)mnx=min(mnx,it.x),mny=min(mny,it.y); up(i,0,3)A[x+1][i]=diff(g[i].x-mnx,g[i].y-mny); } }W[10]; void getit(){ W[1].LIM=1; W[1].A[0][0]=diff(0,0),W[1].A[0][1]=diff(0,1),W[1].A[0][2]=diff(1,1),W[1].A[0][3]=diff(1,2); W[1].rev(0); W[2].LIM=1; W[2].A[0][0]=diff(0,1),W[2].A[0][1]=diff(0,2),W[2].A[0][2]=diff(1,0),W[2].A[0][3]=diff(1,1); W[2].rev(0); W[3].LIM=3; W[3].A[0][0]=diff(0,0),W[3].A[0][1]=diff(1,0),W[3].A[0][2]=diff(1,1),W[3].A[0][3]=diff(1,2); up(i,0,2)W[3].rev(i); W[4].LIM=3; W[4].A[0][0]=diff(1,0),W[4].A[0][1]=diff(1,1),W[4].A[0][2]=diff(1,2),W[4].A[0][3]=diff(0,2); up(i,0,2)W[4].rev(i); W[5].LIM=3; W[5].A[0][0]=diff(0,1),W[5].A[0][1]=diff(1,0),W[5].A[0][2]=diff(1,1),W[5].A[0][3]=diff(1,2); up(i,0,2)W[5].rev(i); W[6].LIM=0; W[6].A[0][0]=diff(0,0),W[6].A[0][1]=diff(0,1),W[6].A[0][2]=diff(1,0),W[6].A[0][3]=diff(1,1); W[7].LIM=1; W[7].A[0][0]=diff(0,0),W[7].A[0][1]=diff(0,1),W[7].A[0][2]=diff(0,2),W[7].A[0][3]=diff(0,3); W[7].rev(0); } struct node { int col,w,x,y; node(int _col,int _w,int _x,int _y){ col=_col,w=_w,x=_x,y=_y; } }; vector<node>opt; bool found(int x){ up(i,1,m)if(!used[g(x,i)])return 1; return 0; } bool found(){ up(i,1,n*m)vis[i]=0; up(i,1,n)up(j,1,m)if((!used[g(i,j)])&&(!vis[g(i,j)])){ queue<pi>q;q.push(m_p(i,j));vis[g(i,j)]=1; int siz=0; while(!q.empty()){ auto it=q.front();q.pop(); ++siz; up(k,0,3){ int nx=it.p1+dx[k],ny=it.p2+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m); else continue; if(vis[g(nx,ny)]||used[g(nx,ny)])continue; vis[g(nx,ny)]=1; q.push(m_p(nx,ny)); } }if(siz%4)return 1; }return 0; } void dfs(int x,int now){ /*if(clock()*1.0/CLOCKS_PER_SEC>0.9){ printf("No\n");exit(0); }*/ if(now>n*m/4){ printf("Yes\n"); for(auto it:opt)printf("%c%d %d %d\n",ss[it.col],it.w,it.x,it.y); exit(0); } if(found())return; up(i,x,min(x+2,n))up(j,1,m){ up(col,1,7){ if(T[col]==NEED)continue; up(w,0,W[col].LIM){ bool fl=1; up(ww,0,3){ int nx=i+W[col].A[w][ww].x; int ny=j+W[col].A[w][ww].y; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&(!used[g(nx,ny)])); else { fl=0;break; } } if(!fl)continue; up(ww,0,3){ int nx=i+W[col].A[w][ww].x; int ny=j+W[col].A[w][ww].y; assert(!used[g(nx,ny)]); used[g(nx,ny)]=1; }++T[col]; opt.p_b(node(col,w,i,j)); dfs(i,now+1); opt.pop_back(); --T[col]; up(ww,0,3){ int nx=i+W[col].A[w][ww].x; int ny=j+W[col].A[w][ww].y; used[g(nx,ny)]=0; } } } } } void slv(){ getit(); n=read(),m=read(); // for (int i = 1; i <= 7; i++) { // for (int j = 0; j <= W[i].LIM; j++) { // for (int k = 0; k <= 3; k++) { // cerr << W[i].A[j][k].x << ' ' << W[i].A[j][k].y << endl; // } // cerr << endl; // } // cerr << endl; // } if((n*m)%28){ printf("No\n");return; }NEED=n*m/28; dfs(1,1); printf("No\n"); }int main(){ slv(); fclose(stdin); fclose(stdout); return 0; } /* (x,y) -> (y,-x) */


测评信息: