QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#883835#5063. FillominoLarunatrecyTL 3ms30288kbC++144.7kb2025-02-05 19:17:562025-02-05 19:18:07

Judging History

This is the latest submission verdict.

  • [2025-02-05 19:18:07]
  • Judged
  • Verdict: TL
  • Time: 3ms
  • Memory: 30288kb
  • [2025-02-05 19:17:56]
  • 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;
}
void solve()
{
	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);
	x1--;y1--;x2--;y2--;x3--;y3--;
	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);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	a[i][j]=0;
	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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 30288kb

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:

ACC
BBC
BCC
AAAA
BABB
BCCC
BCCC

result:

ok ok (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

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:


result: