QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883924#5063. FillominoLarunatrecyTL 209ms28272kbC++146.1kb2025-02-05 19:55:262025-02-05 19:55:35

Judging History

This is the latest submission verdict.

  • [2025-02-05 19:55:35]
  • Judged
  • Verdict: TL
  • Time: 209ms
  • Memory: 28272kb
  • [2025-02-05 19:55:26]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
const int N = 550;
const int M = N*N;
int vis[M],dep[M];
int gmin(int x,int y){if(!x||!y)return x+y;return dep[x]<dep[y]?x:y;}
vector<int> lst[M];
int fa[M],deg[M],low[M];
vector<int> G[M];
void dfs(int x)
{
	vis[x]=1;
	low[x]=0;
	for(int y:G[x])if(!vis[y])
	{
		dep[y]=dep[x]+1;
		dfs(y);
		low[x]=gmin(low[x],low[y]);
		deg[x]++;
		fa[y]=x;
	}
	else if(dep[y]<dep[x])
	{
		low[x]=gmin(low[x],y);
	}
}
int used[M],perm[M],seq[M],pos[M];
int test=0,ot=0,cnt=0;
void dfs2(int x)
{
	perm[++cnt]=x;pos[x]=cnt;
	vis[x]=1;
	for(int y:lst[x])if(!vis[y])dfs2(y);
}
void solve(int n,int s,int t)
{
	for(int i=1;i<=n;i++)lst[i].clear(),fa[i]=deg[i]=dep[i]=vis[i]=0;
	dep[1]=0;
	dfs(s);
	queue<int> q;
	for(int i=1;i<=n;i++)vis[i]=0;
	int c=0;
	int u=t;while(u)vis[u]=1,seq[++c]=u,u=fa[u];
	for(int i=1;i<=n;i++)
	if(i!=t&&deg[i]==0)q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		lst[fa[x]].push_back(x);
		lst[low[x]].push_back(x);
		deg[fa[x]]--;
		if(!deg[fa[x]]&&!vis[fa[x]])q.push(fa[x]); 
	}
	for(int i=1;i<=n;i++)used[i]=perm[i]=0;
	cnt=0;
	for(int i=c;i>=1;i--)
	{
		int u=seq[i];
		dfs2(u);
	}
}
int a[N][N],b[N][N],id[N][N],idx=0;
int n,m;
inline int roln(int x){return (x%n+n)%n;}
inline int rolm(int y){return (y%m+m)%m;}
struct node 
{
	int tp,x,y;
};
bool operator <(node a,node b)
{
	return a.tp<b.tp;
}
int dX=0,dY=0;
int nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int get(int x,int y)
{
	int H=0,C=0;
	for(int k=0;k<4;k++)
	{
		int dx=roln(x+nxt[k][0]);
		int dy=rolm(y+nxt[k][1]);
		if(a[dx][dy]!=1)
		C++,H|=(1<<k);
	}
	if(C==1)return 3;
	if(C==2&&H!=3&&H!=12)return 2;
	return 1;
}
bool F=0;
bool bok[N][N],sig[N][N];
bool check()
{
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	bok[i][j]=0;
	queue<pair<int,int>>q;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(sig[i][j])q.push({i,j}),bok[i][j]=1;
	while(!q.empty())
	{
		auto u=q.front();
		q.pop();
		int x=u.first,y=u.second;
		for(int k=0;k<4;k++)
		{
			int dx=roln(x+nxt[k][0]);
			int dy=rolm(y+nxt[k][1]);
			if(a[dx][dy]==a[x][y]&&!bok[dx][dy])
			bok[dx][dy]=1,q.push({dx,dy});
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(!bok[i][j])return 0;
	return 1;
}
void dfs(int x,int y,int c1,int c2,int c3)
{
	if(F)return;
	if(y==m)
	{
		if(x==n-1)
		{
			if(check())F=1;
			return;
		}
		dfs(x+1,0,c1,c2,c3);
		return;
	}
	for(int t=1;t<=3;t++)
	{
		if(a[x][y]&&a[x][y]!=t)continue;
		if(t==1&&c1==0)continue;
		if(t==2&&c2==0)continue;
		if(t==3&&c3==0)continue;
		int u=a[x][y];a[x][y]=t;
		if(t==1)c1--;if(t==2)c2--;if(t==3)c3--;
		dfs(x,y+1,c1,c2,c3);
		if(F)return;
		if(t==1)c1++;if(t==2)c2++;if(t==3)c3++;
		a[x][y]=u;
	}
}
bool flag=0;
void solve()
{
	int C1,C2,C3,x1,y1,x2,y2,x3,y3;
	read(n);read(m);
	if(test==0&&m>3)flag=1;
	read(C1);read(C2);read(C3);
	read(x1);read(y1);read(x2);read(y2);read(x3);read(y3);
	++test;
	if(test==1300&&flag)exit(0);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	a[i][j]=0;
	x1--;y1--;x2--;y2--;x3--;y3--;
	if(n==3&&m==3)
	{
		a[x1][y1]=1;
		a[x2][y2]=2;
		a[x3][y3]=3;
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		sig[i][j]=a[i][j];
		F=0;
		dfs(0,0,C1,C2,C3);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			putchar('A'+a[i][j]-1);
			printf("\n");
		}
		return;
	}
	char A='A',B='B',C='C';
	if(C1>C2)swap(C1,C2),swap(x1,x2),swap(y1,y2),swap(A,B);
	if(C1>C3)swap(C1,C3),swap(x1,x3),swap(y1,y3),swap(A,C);
	a[x1][y1]=1;a[x2][y2]=2;a[x3][y3]=3;
	bool flag=0;
	dX=x1;dY=y1;
	x1=roln(x1-dX);y1=rolm(y1-dY);
	x2=roln(x2-dX);y2=rolm(y2-dY);
	x3=roln(x3-dX);y3=rolm(y3-dY);
	if(x2>x3)swap(x2,x3),swap(y2,y3),swap(B,C),swap(C2,C3);
	int cur=C1; 
	auto chk = [&](int c,int p)
	{
		if(flag)return;
		if(c==1)
		{
			if(p==x2||p==x3)return;
			flag=1;
			for(int j=0,q=y1;j<m;j++,q=rolm(q+1))
			{
				cur--;
				if(!a[p][q])a[p][q]=5;
				if(!cur)break;
			}
		}	
		else 
		{
			if(p==y2||p==y3)return;
			flag=1;
			for(int i=0,q=x1;i<n;i++,q=roln(q+1))
			{
				cur--;
				if(!a[q][p])a[q][p]=5;
				if(!cur)break;
			}
		}
	};
	if(cur)
	{
		
		for(int i=x2;i<=x3;i++)a[i][y2]=4;
		for(int i=min(y2,y3);i<=max(y2,y3);i++)a[x3][i]=4;
		a[x2][y2]=2;a[x3][y3]=3;
		for(int x=x1-1;x<=x1+1;x++)chk(1,roln(x));
		for(int y=y1-1;y<=y1+1;y++)chk(2,rolm(y));
//		for(int i=0;i<n;i++)
//		{
//			
//			for(int j=0;j<m;j++)
//			{
//				cout<<a[i][j];
//			}
//			cout<<endl;
//		}
//		cout<<endl;
		priority_queue<node>Q;
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)
		if(a[i][j]==5)a[i][j]=0,Q.push({4,i,j});
		cur=C1;a[0][0]=0;Q.push({5,0,0});
		while(cur)
		{
			auto u=Q.top();
			Q.pop();
			int x=u.x,y=u.y;
			if(a[x][y])continue;
			a[x][y]=1;
			cur--;
			for(int k=0;k<4;k++)
			{
				int dx=roln(x+nxt[k][0]);
				int dy=rolm(y+nxt[k][1]);
				if(a[dx][dy])continue;
				Q.push({get(dx,dy),dx,dy});
			}
		}
	}
//	for(int i=0;i<n;i++)
//	{
//		
//		for(int j=0;j<m;j++)
//		{
//			cout<<a[i][j];
//		}
//		cout<<endl;
//	}
	idx=0;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	if(a[i][j]!=1)id[i][j]=++idx;
	else id[i][j]=0;
	for(int i=1;i<=idx;i++)G[i].clear();
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(id[i][j])
	{
		for(int k=0;k<4;k++)
		{
			int x=roln(i+nxt[k][0]);
			int y=rolm(j+nxt[k][1]);
			if(id[x][y])
			G[id[i][j]].push_back(id[x][y]);
		}
	}
	solve(idx,id[x2][y2],id[x3][y3]);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	if(id[i][j])
	{
		if(pos[id[i][j]]<=C2)a[i][j]=2;
		else a[i][j]=3;
	} 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			int x=roln(i-dX);
			int y=rolm(j-dY);
			if(a[x][y]==1)putchar(A);
			else if(a[x][y]==2)putchar(B);
			else putchar(C);
		}
		putchar('\n');
	}
}
int main()
{
	int T;
	read(T);
	while(T--)
	{
		solve();
	}
	return 0;
}
/*
5
10 10
33 33 34
1 1 9 9 4 6
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 28272kb

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
AAAA
BABB
BCCC
BCCC

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 209ms
memory: 22100kb

input:

100000
3 3
2 1 6
3 3
1 2
2 2
3 3
7 1 1
3 1
1 1
2 3
3 3
1 7 1
1 1
3 1
1 3
3 3
2 1 6
3 3
1 3
1 1
3 3
7 1 1
2 1
3 2
1 1
3 3
3 2 4
2 2
2 1
1 2
3 3
3 2 4
3 3
1 1
2 1
3 3
2 4 3
2 1
1 2
1 3
3 3
3 5 1
1 2
3 1
2 2
3 3
2 4 3
1 1
2 1
2 3
3 3
1 5 3
3 3
2 2
1 2
3 3
5 1 3
2 1
1 2
2 2
3 3
3 5 1
2 1
2 3
3 2
3 3
7 1...

output:

CBA
CCC
CCA
BAA
AAC
AAA
ABC
BBB
BBB
CCB
CCA
CCA
CAA
AAA
ABA
BCA
BAA
CCC
BAA
CCC
BCA
ABC
ABB
CBC
AAA
BCB
BBB
AAB
BCC
BCB
BCB
BBB
CCA
ABA
ACA
ACC
AAB
ABB
BCB
BAA
AAC
AAA
BAB
BAB
CBB
BCB
BBB
ABB
AAB
CCC
CBB
AAB
BBC
ABB
AAA
BBB
BCB
BAA
CCC
CAC
BAA
AAC
CAC
BBB
CBC
ABC
AAA
BAC
ACC
BCC
ACC
CCC
AAB
CCB
CCC
...

result:

ok ok (100000 test cases)

Test #3:

score: -100
Time Limit Exceeded

input:

51263
3 10
19 7 4
1 1
2 7
2 9
3 7
1 5 15
1 6
2 2
2 7
3 3
1 2 6
1 3
3 1
2 2
3 6
13 1 4
2 1
2 6
3 6
3 8
10 10 4
2 8
1 5
3 1
3 5
11 3 1
1 3
2 4
2 5
3 10
14 9 7
2 2
1 2
3 1
3 9
3 2 22
3 6
2 7
2 1
3 10
12 6 12
3 5
2 9
2 5
3 3
2 6 1
1 3
2 1
1 2
3 10
10 14 6
2 10
1 4
1 9
3 8
3 20 1
2 6
1 1
1 2
3 10
13 3 14...

output:

AAAAABAAAA
AAAAABBBCA
CAAABBABCC
BCCACAB
BBCCCCC
BCCCCCC
BCA
CCC
BCC
AAAACC
AAAAAB
AAAABC
BBBBBAAA
CBBBBAAA
CCCCBAAA
AAAAA
AABBC
AABAA
BBAAAAAABB
CAAAAAAABB
CBCCCCCBBC
CCCCCCCBC
CCCCACBCC
CCCCAACCC
BBCBAAAABB
CCCCCAAABC
CCCCAABAAC
ACA
BBB
BBB
BBBBBBCACB
BBBBBAAAAA
CBCCBAAACC
BCCBBABB
BBBBBABB
BBBBBB...

result: