QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884161#5063. FillominoLarunatrecyWA 207ms30424kbC++147.4kb2025-02-05 21:41:092025-02-05 21:41:10

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:41:10]
  • Judged
  • Verdict: WA
  • Time: 207ms
  • Memory: 30424kb
  • [2025-02-05 21:41:09]
  • 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&&n>3)flag=1;
	if(flag&&test<1176)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: 0ms
memory: 28404kb

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: 207ms
memory: 28364kb

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: 108ms
memory: 30424kb

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: 3ms
memory: 26192kb

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:

7 3
10 6 5
3 2 2 2 2 3

result:

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