QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521168#5063. FillominoCrysflyWA 3ms73320kbC++176.3kb2024-08-15 23:00:222024-08-15 23:00:23

Judging History

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

  • [2024-08-15 23:00:23]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:73320kb
  • [2024-08-15 23:00:22]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000006
#define inf 0x3f3f3f3f

#define y1 __ssd
#define N 1005
int n,m,c1,c2,c3,x1,y1,x2,y2,x3,y3;
char t1,t2,t3;
int a[N][N];
int dx[5]={0,1,0,-1},dy[4]={1,0,-1,0};

int id[N][N];

struct node{
	int x,y,d,op;
	bool operator <(const node &b)const{
		if(op!=b.op) return op<b.op;
		return d<b.d;
	}
};

int dis[N][N];
bool corner(int x,int y,int nd){
	int s=0,c=0;
	For(d,0,3){
		int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
		if(a[xx][yy]) s|=(1<<d),c++;
	}
	if(nd==3)return c==3;
	if(nd==2)return c>=2 && (!(s==5||s==10));
	assert(0);
}

int dfn[maxn],low[maxn],fa[maxn],idx,que[maxn],on[maxn];
vi e[maxn],p[maxn];
int cut[maxn];
bool vis[maxn];
void tar(int u,int pa){
	fa[u]=pa;
	dfn[u]=low[u]=++idx,que[idx]=u;
	int ch=0;
	for(auto v:e[u]){
		if(v==pa)continue;
		if(!dfn[v]){
			tar(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u] && pa) cut[u]=1;
			++ch;
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(!pa && ch>1) cut[u]=1;
}

int q[maxn],len,tim[maxn];
void dfs(int u){
	vis[u]=1;
	q[++len]=u,tim[u]=len;
	for(int v:p[u]) if(!vis[v]) dfs(v);
}
void bipolar(int n,int s,int t){
//	cout<<"bipolar "<<n<<" "<<s<<" "<<t<<"\n";
	For(i,0,n) dfn[i]=low[i]=fa[i]=cut[i]=vis[i]=on[i]=0,p[i].clear(); 
	idx=0,len=0;
	tar(s,0);
	vi path;
	for(int x=t;x;x=fa[x]) on[x]=1,path.pb(x);
	reverse(ALL(path));
	Rep(i,n,1){
		int u=que[i];
		if(!on[u]) p[fa[u]].pb(u),p[que[low[u]]].pb(u);
	}
	for(int x:path) dfs(x);
}

bool give(int cto){
	For(i,0,n-1)For(j,0,m-1)
		if(a[i][j]==1 && mkp(i,j)!=mkp(x1,y1)){
			For(d,0,3){
				int ii=(i+dx[d])%n,jj=(j+dy[d])%m;
				if(a[ii][jj]==cto){
					a[i][j]=cto;
					return 1;
				}
			}
		}
	return 0;
}

bool vs[N][N],flag;
void DFS(int x,int y){
	vs[x][y]=1;
	For(d,0,4){
		int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
		if(!vs[xx][yy] && a[xx][yy]==a[x][y]) DFS(xx,yy);
	}
}
bool chk(){
//	cout<<"chk\n";
	For(i,0,n-1)For(j,0,m-1)vs[i][j]=0;
	DFS(x1,y1),DFS(x2,y2),DFS(x3,y3);
	For(i,0,n-1)For(j,0,m-1)if(!vs[i][j])return 0;
	return 1;
}
void dfs(int x,int y,int r1,int r2,int r3){
	if(r1<0 || r2<0 || r3<0) return;
	if(flag)return;
//	cout<<"dfs "<<x<<" "<<y<<" "<<r1<<" "<<r2<<" "<<r3<<"\n";
	if(x==n){
		if(chk())flag=1;
		return;
	}
	#define GO dfs(x+(y==m-1),(y+1)%m,r1,r2,r3); if(flag) return;
	if(mkp(x,y)!=mkp(x1,y1) && mkp(x,y)!=mkp(x2,y2) && mkp(x,y)!=mkp(x3,y3)) {
		--r1,a[x][y]=1; GO; ++r1; 
		--r2,a[x][y]=2; GO; ++r2;
		--r3,a[x][y]=3; GO; ++r3;
	}else{
		GO;
	}
}

int vx[N],vy[N];

void work(int O)
{
	n=read(),m=read();
	dx[3]=n-1,dy[2]=m-1;
	c1=read(),c2=read(),c3=read();
	x1=read(),y1=read(),x2=read(),y2=read(),x3=read(),y3=read();
	--x1,--y1,--x2,--y2,--x3,--y3;
	
	if(n<=3 && m<=3){
		flag=0;
		a[x1][y1]=1,a[x2][y2]=2,a[x3][y3]=3;
		dfs(0,0,c1-1,c2-1,c3-1);
		assert(flag);
		string out=" ABC";
		For(i,0,n-1){
			For(j,0,m-1)putchar(out[a[i][j]]);
			puts("");
		}
		return ;
	}
	
	if(O>=3){
		if(O==20){
			cout<<n<<" "<<m<<"\n";
			cout<<c1<<" "<<c2<<" "<<c3<<"\n";
			cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<"\n";
			exit(0);
		}return;
	}
	
	t1='A',t2='B',t3='C';
	if(c1>c2) swap(c1,c2),swap(x1,x2),swap(y1,y2),swap(t1,t2);
	if(c1>c3) swap(c1,c3),swap(x1,x3),swap(y1,y3),swap(t1,t3);
	
	auto gdis=[&](int x,int y,int xx,int yy){
		return min(abs(x-xx),n-1-abs(x-xx)) + min(abs(y-yy),m-1-abs(y-yy));
	};
	
	For(i,0,n-1) For(j,0,m-1) a[i][j]=id[i][j]=0;
	For(i,0,n-1) For(j,0,m-1) 
		dis[i][j]=min(gdis(x2,y2,i,j),gdis(x3,y3,i,j));
		
	For(i,0,n-1){
		For(j,0,m-1) cout<<dis[i][j]<<" "; cout<<"\n";
	}
	
	a[x2][y2]=2;
	a[x3][y3]=3;
	
	For(i,0,n-1) vx[i]=0;
	For(i,0,m-1) vy[i]=0;
	vx[x2]=vx[x3]=1;
	vx[y2]=vx[y3]=1;
	
	priority_queue<node>q;
	q.push((node){x1,y1,dis[x1][y1],5});
	
	bool qwq=0;
	for(int xx:{x1,(x1+1)%n,(x1+n-1)%n})
		if(!qwq && !vx[xx]){
			For(y,0,m-1) q.push((node){xx,(y1+y)%m,dis[xx][(y1+y)%m],4});
			qwq=1; break;
		}
	for(int yy:{y1,(y1+1)%m,(y1+m-1)%m}){
		if(!qwq && !vy[yy]){
			For(x,0,n-1) q.push((node){(x1+x)%m,yy,dis[(x1+x)%m][yy],4});
			qwq=1; break;
		}
	}
	
	int now1=0;
	while(now1<c1 || (q.size() && q.top().op==2)){
		auto [x,y,dd,op]=q.top(); q.pop();
		if(a[x][y]) continue;
	//	cout<<"add "<<x<<" "<<y<<"\n";
		a[x][y]=1;
		++now1;
		For(d,0,3){
			int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
			if(!a[xx][yy]){
				int op2=0;
				if(corner(xx,yy,3)) op2=2;
				else if(corner(xx,yy,2)) op2=1;
				q.push((node){xx,yy,dis[xx][yy],op2});
	//			cout<<"push "<<xx<<" "<<yy<<" "<<op2<<"\n";
			}
		}
	}
	
	
	cerr<<"now1 "<<now1<<"\n";
	For(i,0,n-1){
		For(j,0,m-1)cerr<<a[i][j];
		cerr<<"\n";
	}
	
	a[x2][y2]=a[x3][y3]=0;
	idx=0;
	For(i,0,n-1)For(j,0,m-1)if(!a[i][j])id[i][j]=++idx;
	For(i,0,idx) e[i].clear();
	auto add=[&](int u,int v){
		e[u].pb(v),e[v].pb(u);
	};
	For(i,0,n-1)For(j,0,m-1){
		if(id[i][j] && id[(i+1)%n][j]) add(id[i][j],id[(i+1)%n][j]);
		if(id[i][j] && id[i][(j+1)%m]) add(id[i][j],id[i][(j+1)%m]);
	}
	bipolar(idx,id[x2][y2],id[x3][y3]);
//	For(i,1,idx) cout<<tim[i]<<" "; cout<<"\n";
	
	For(i,0,n-1) For(j,0,m-1) 
		if(id[i][j]) a[i][j]=(tim[id[i][j]]<=c2?2:3);
	if(now1>c1){
		if(!give(3)){
			For(i,0,n-1) For(j,0,m-1) 
				if(id[i][j]) a[i][j]=(tim[id[i][j]]<c2?2:3);
			give(2);
		}
	}
	string out=" "; out+=t1,out+=t2,out+=t3;
	For(i,0,n-1){
		For(j,0,m-1)putchar(out[a[i][j]]);
		puts("");
	}
}

signed main()
{
	int T=read();
	For(_,1,T)work(_);
	return 0;
}
/*
3 10
10 7 13
1 1 2 5 3 9


2
3 3
1 3 5
1 1
2 2
3 3
4 4
5 5 6
2 2
2 3
3 3
*/

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 73320kb

input:

2
3 3
1 3 5
1 1
2 2
3 3
4 4
5 5 6
2 2
2 3
3 3

output:

ABB
CBC
CCC
2 2 1 2 
1 1 0 1 
1 1 0 1 
2 2 1 2 
AAAA
CABB
CCCB
CCBB

result:

wrong answer Line "2 2 1 2 " doesn't correspond to pattern "[A-C]{3,500}" (test case 2)