QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884002#5063. FillominoLarunatrecyWA 209ms32460kbC++146.4kb2025-02-05 20:42:392025-02-05 20:42:40

Judging History

This is the latest submission verdict.

  • [2025-02-05 20:42:40]
  • Judged
  • Verdict: WA
  • Time: 209ms
  • Memory: 32460kb
  • [2025-02-05 20:42:39]
  • 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()
{
	++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<22)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; 
	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;
			for(int j=0,q=y1;j<m&&cur;j++,q=rolm(q+1))
			{
				if(!a[p][q])a[p][q]=5,cur--;
			}
		}	
		else 
		{
			for(int j=0;j<n;j++)if(a[j][p]&&a[j][p]!=1)return;
			flag=1;
			cur--;
			for(int i=0,q=x1;i<n&&cur;i++,q=roln(q+1))
			{
				if(!a[q][p])a[q][p]=5,cur--;
				if(!cur)break;
			}
		}
	};
	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;
//	}
	if(cur)
	{
		
//		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});
			}
		}
	}
	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++)
	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: 3ms
memory: 32460kb

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: 24272kb

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
Wrong Answer
time: 107ms
memory: 30416kb

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:

wrong answer C''s size should be 7 instead of 6 (test case 995)