QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884159#5063. FillominoLarunatrecyWA 208ms32456kbC++147.5kb2025-02-05 21:40:232025-02-05 21:40:24

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:40:24]
  • Judged
  • Verdict: WA
  • Time: 208ms
  • Memory: 32456kb
  • [2025-02-05 21:40:23]
  • 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],ban[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;
bool adjust(int u,int v)
{
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	if(!sig[i][j]&&a[i][j]==u&&!ban[i][j])
	{
		for(int k=0;k<4;k++)
		{
			int x=roln(i+nxt[k][0]);
			int y=rolm(j+nxt[k][1]);
			if(a[x][y]==v)
			{
				a[i][j]=v;
				return 1;
			}
		}
	}
	return 0;
}
void solve()
{
	++test;
	int C1,C2,C3,x1,y1,x2,y2,x3,y3;
	read(n);read(m);
	read(C1);read(C2);read(C3);
	read(x1);read(y1);read(x2);read(y2);read(x3);read(y3);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	a[i][j]=0;
//	if(test==1&&m>3)flag=1;
//	if(flag&&test<2036)return;
//	if(flag)
//	{
//		cout<<n<<' '<<m<<endl;
//		cout<<C1<<' '<<C2<<' '<<C3<<endl;
//		cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<x3<<' '<<y3<<endl;
//		exit(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);
	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);
	a[x1][y1]=1;a[x2][y2]=2;a[x3][y3]=3;
	if(x2>x3)swap(x2,x3),swap(y2,y3),swap(B,C),swap(C2,C3);
	int cur=C1; 
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	sig[i][j]=a[i][j];
	bool spe=0;
	auto chk = [&](int c,int p)
	{
		if(flag)return;
		if(c==1)
		{
			for(int j=0;j<m;j++)if(a[p][j]&&a[p][j]!=1)return;
			cur--;
			flag=1;
			int c=0;
			for(int j=0,q=y1;j<m&&cur;j++,q=rolm(q+1))
			{
				c++;
				if(!a[p][q])a[p][q]=5,cur--;
			}
			if(c==m-1)
			{
				spe=1;
				for(int i=0;i<m;i++)a[p][i]=1;
			}
		}	
		else 
		{
			for(int j=0;j<n;j++)if(a[j][p]&&a[j][p]!=1)return;
			flag=1;
			cur--;
			int c=0;
			for(int i=0,q=x1;i<n&&cur;i++,q=roln(q+1))
			{
				c++;
				if(!a[q][p])a[q][p]=5,cur--;
			}
			if(c==n-1)
			{
				spe=1;
				for(int i=0;i<n;i++)a[i][p]=1;
			}
		}
	};
	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));
	if(cur)
	{
		
		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});
			}
		}
		while(!Q.empty())
		{
			
			auto u=Q.top();
			Q.pop();
			int x=u.x,y=u.y;
			if(a[x][y])continue;
			if(u.tp==3)
			{
				a[x][y]=1;
				spe=1;
				break;
			}
		}
		
	}
	else 
	{
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		if(a[i][j]==5)a[i][j]=1;
	}
	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++)ban[i][j]=0;
	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;
	} 
	vector<pair<int,int> > slp;
	for(int k=0;k<4;k++)
	{
		int x=roln(nxt[k][0]),y=rolm(nxt[k][1]);
		if(a[x][y]==1)slp.push_back({x,y});
	}
	if(slp.size()==1)
	{
		for(auto u:slp)
		ban[u.first][u.second]=1;
	}
	if(spe)
	{
		if(adjust(1,3));
		else 
		{
			
			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++)
//			{
//				cout<<a[i][j];
//			}
//			cout<<endl;
//		}
			adjust(1,2);
		}
	}
	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;
}
/*
1
3 6
2 14 2
3 6 2 5 3 5


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 208ms
memory: 28236kb

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: 0
Accepted
time: 109ms
memory: 30300kb

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:

AAAAABBCAA
AAAAABBCCA
AAAABBBCAA
BCCCCAB
BBCCCCC
BCCCCCC
BCA
CCC
BCC
AAAACA
AAAACB
AAAACC
BBBBBAAA
BBBBBAAA
CCCCAAAA
AAAAA
AABBC
AABAA
BBAAAAAABB
BAAAAAAABB
CCCCCCCABB
CCCCCCBCC
CCCCACBCC
CCCCAACCC
BBBCAAAABB
CCCCCAAABC
CCCCAAAAAC
ACA
BBB
BBB
BBBBBAAACB
BBBBBBAAAA
CCCBBAAACC
BCBBABBB
BBBBAABB
BBBBBB...

result:

ok ok (51263 test cases)

Test #4:

score: -100
Wrong Answer
time: 111ms
memory: 32456kb

input:

51131
5 3
9 2 4
4 2
4 1
1 1
9 3
2 18 7
6 3
8 2
3 3
9 3
5 15 7
5 3
4 2
1 1
10 3
1 25 4
3 1
1 2
4 2
8 3
9 8 7
6 3
3 1
1 1
9 3
15 9 3
5 1
6 3
2 3
8 3
6 4 14
7 2
6 3
4 3
6 3
10 6 2
3 2
4 3
1 2
7 3
5 2 14
1 2
5 1
2 1
9 3
4 1 22
2 3
4 2
9 2
3 3
7 1 1
1 2
1 1
2 3
4 3
5 6 1
2 3
1 1
2 1
10 3
20 6 4
2 2
5 2
2...

output:

CAC
CAC
BAA
BAA
AAA
BBC
BBC
BBC
BBB
BBA
BBA
BCC
BBC
BBC
CBC
BBC
BBC
BBB
BAA
AAA
CBB
CBB
CBB
BBB
BBB
ABB
CCB
CBB
CBB
BBB
BBB
BBB
BBB
CCC
BBB
BBB
ABA
ABA
AAA
CAA
CCC
BCC
BBC
BAB
BAB
AAB
AAB
AAA
AAA
AAA
ACC
CCC
CCC
CCC
BBB
AAB
AAC
ACC
ACB
AAB
AAB
AAB
AAB
ACB
CAC
CAC
AAC
BAC
BCC
CCC
CCC
CCA
CCA
CCC
CBC
...

result:

wrong answer Pos (3,2) is not A (test case 1176)