QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521179#5063. FillominoCrysflyWA 343ms73516kbC++176.3kb2024-08-15 23:10:042024-08-15 23:10:06

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 23:10:06]
  • 评测
  • 测评结果:WA
  • 用时:343ms
  • 内存:73516kb
  • [2024-08-15 23:10:04]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000006
#define inf 0x3f3f3f3f

#define y1 __ssd
#define N 1005
int T;
int n,m,c1,c2,c3,x1,y1,x2,y2,x3,y3;
char t1,t2,t3;
int a[N][N];
int dx[5]={0,1,0,-1},dy[4]={1,0,-1,0};

int id[N][N];

struct node{
	int x,y,d,op;
	bool operator <(const node &b)const{
		if(op!=b.op) return op<b.op;
		return d<b.d;
	}
};

int dis[N][N];
bool corner(int x,int y,int nd){
	int s=0,c=0;
	For(d,0,3){
		int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
		if(a[xx][yy]==1) s|=(1<<d),c++;
	}
	if(nd==3)return c==3;
	if(nd==2)return c>=2 && (!(s==5||s==10));
	assert(0);
}

int dfn[maxn],low[maxn],fa[maxn],idx,que[maxn],on[maxn];
vi e[maxn],p[maxn];
int cut[maxn];
bool vis[maxn];
void tar(int u,int pa){
	fa[u]=pa;
	dfn[u]=low[u]=++idx,que[idx]=u;
	int ch=0;
	for(auto v:e[u]){
		if(v==pa)continue;
		if(!dfn[v]){
			tar(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u] && pa) cut[u]=1;
			++ch;
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(!pa && ch>1) cut[u]=1;
}

int q[maxn],len,tim[maxn];
void dfs(int u){
	vis[u]=1;
	q[++len]=u,tim[u]=len;
	for(int v:p[u]) if(!vis[v]) dfs(v);
}
void bipolar(int n,int s,int t){
//	cout<<"bipolar "<<n<<" "<<s<<" "<<t<<"\n";
	For(i,0,n) dfn[i]=low[i]=fa[i]=cut[i]=vis[i]=on[i]=0,p[i].clear(); 
	idx=0,len=0;
	tar(s,0);
	vi path;
	for(int x=t;x;x=fa[x]) on[x]=1,path.pb(x);
	reverse(ALL(path));
	Rep(i,n,1){
		int u=que[i];
		if(!on[u]) p[fa[u]].pb(u),p[que[low[u]]].pb(u);
	}
	for(int x:path) dfs(x);
}

bool give(int cto){
	For(i,0,n-1)For(j,0,m-1)
		if(a[i][j]==1 && mkp(i,j)!=mkp(x1,y1)){
			For(d,0,3){
				int ii=(i+dx[d])%n,jj=(j+dy[d])%m;
				if(a[ii][jj]==cto){
					a[i][j]=cto;
					return 1;
				}
			}
		}
	return 0;
}

bool vs[N][N],flag;
void DFS(int x,int y){
	vs[x][y]=1;
	For(d,0,4){
		int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
		if(!vs[xx][yy] && a[xx][yy]==a[x][y]) DFS(xx,yy);
	}
}
bool chk(){
//	cout<<"chk\n";
	For(i,0,n-1)For(j,0,m-1)vs[i][j]=0;
	DFS(x1,y1),DFS(x2,y2),DFS(x3,y3);
	For(i,0,n-1)For(j,0,m-1)if(!vs[i][j])return 0;
	return 1;
}
void dfs(int x,int y,int r1,int r2,int r3){
	if(r1<0 || r2<0 || r3<0) return;
	if(flag)return;
//	cout<<"dfs "<<x<<" "<<y<<" "<<r1<<" "<<r2<<" "<<r3<<"\n";
	if(x==n){
		if(chk())flag=1;
		return;
	}
	#define GO dfs(x+(y==m-1),(y+1)%m,r1,r2,r3); if(flag) return;
	if(mkp(x,y)!=mkp(x1,y1) && mkp(x,y)!=mkp(x2,y2) && mkp(x,y)!=mkp(x3,y3)) {
		--r1,a[x][y]=1; GO; ++r1; 
		--r2,a[x][y]=2; GO; ++r2;
		--r3,a[x][y]=3; GO; ++r3;
	}else{
		GO;
	}
}

int vx[N],vy[N];

void work(int O)
{
	n=read(),m=read();
	dx[3]=n-1,dy[2]=m-1;
	c1=read(),c2=read(),c3=read();
	x1=read(),y1=read(),x2=read(),y2=read(),x3=read(),y3=read();
	
//	if(T==51263  &&  O>=3){
//		if(O==1642){
//			cout<<n<<" "<<m<<"\n";
//			cout<<c1<<" "<<c2<<" "<<c3<<"\n";
//			cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<"\n";
//			exit(0);
//		}return;
//	}
	
	--x1,--y1,--x2,--y2,--x3,--y3;
	
	if(n<=3 && m<=3){
		flag=0;
		a[x1][y1]=1,a[x2][y2]=2,a[x3][y3]=3;
		dfs(0,0,c1-1,c2-1,c3-1);
		assert(flag);
		string out=" ABC";
		For(i,0,n-1){
			For(j,0,m-1)putchar(out[a[i][j]]);
			puts("");
		}
		return ;
	}
	
	t1='A',t2='B',t3='C';
	if(c1>c2) swap(c1,c2),swap(x1,x2),swap(y1,y2),swap(t1,t2);
	if(c1>c3) swap(c1,c3),swap(x1,x3),swap(y1,y3),swap(t1,t3);
	
	auto gdis=[&](int x,int y,int xx,int yy){
		return min(abs(x-xx),n-1-abs(x-xx)) + min(abs(y-yy),m-1-abs(y-yy));
	};
	
	For(i,0,n-1) For(j,0,m-1) a[i][j]=id[i][j]=0;
	For(i,0,n-1) For(j,0,m-1) 
		dis[i][j]=min(gdis(x2,y2,i,j),gdis(x3,y3,i,j));
		
//	For(i,0,n-1){
//		For(j,0,m-1) cout<<dis[i][j]<<" "; cout<<"\n";
//	}
	
	a[x2][y2]=2;
	a[x3][y3]=3;
	
	For(i,0,n-1) vx[i]=0;
	For(i,0,m-1) vy[i]=0;
	vx[x2]=vx[x3]=1;
	vy[y2]=vy[y3]=1;
	
	priority_queue<node>q;
	q.push((node){x1,y1,dis[x1][y1],5});
	
	bool qwq=0;
	for(int xx:{x1,(x1+1)%n,(x1+n-1)%n})
		if(!qwq && !vx[xx]){
	//		cout<<"XX "<<xx<<"\n";
			For(y,0,m-1) q.push((node){xx,(y1+y)%m,-y,4});
			qwq=1; break;
		}
	for(int yy:{y1,(y1+1)%m,(y1+m-1)%m}){
		if(!qwq && !vy[yy]){
			For(x,0,n-1) q.push((node){(x1+x)%m,yy,-x,4});
			qwq=1; break;
		}
	}
	
	int now1=0;
	while(now1<c1 || (q.size() && q.top().op==2)){
		auto [x,y,dd,op]=q.top(); q.pop();
		if(a[x][y]) continue;
	//	cout<<"add "<<x<<" "<<y<<"\n";
		a[x][y]=1;
		++now1;
		For(d,0,3){
			int xx=(x+dx[d])%n,yy=(y+dy[d])%m;
			if(!a[xx][yy]){
				int op2=0;
				if(corner(xx,yy,3)) op2=2;
				else if(corner(xx,yy,2)) op2=1;
				q.push((node){xx,yy,dis[xx][yy],op2});
	//			cout<<"push "<<xx<<" "<<yy<<" "<<op2<<"\n";
			}
		}
	}
	
	
	cerr<<"now1 "<<now1<<"\n";
	For(i,0,n-1){
		For(j,0,m-1)cerr<<a[i][j];
		cerr<<"\n";
	}
	
	a[x2][y2]=a[x3][y3]=0;
	idx=0;
	For(i,0,n-1)For(j,0,m-1)if(!a[i][j])id[i][j]=++idx;
	For(i,0,idx) e[i].clear();
	auto add=[&](int u,int v){
		e[u].pb(v),e[v].pb(u);
	};
	For(i,0,n-1)For(j,0,m-1){
		if(id[i][j] && id[(i+1)%n][j]) add(id[i][j],id[(i+1)%n][j]);
		if(id[i][j] && id[i][(j+1)%m]) add(id[i][j],id[i][(j+1)%m]);
	}
	bipolar(idx,id[x2][y2],id[x3][y3]);
//	For(i,1,idx) cout<<tim[i]<<" "; cout<<"\n";
	
	For(i,0,n-1) For(j,0,m-1) 
		if(id[i][j]) a[i][j]=(tim[id[i][j]]<=c2?2:3);
	if(now1>c1){
		if(!give(3)){
			For(i,0,n-1) For(j,0,m-1) 
				if(id[i][j]) a[i][j]=(tim[id[i][j]]<c2?2:3);
			give(2);
		}
	}
	string out=" "; out+=t1,out+=t2,out+=t3;
	For(i,0,n-1){
		For(j,0,m-1)putchar(out[a[i][j]]);
		puts("");
	}
}

signed main()
{
	T=read();
	For(_,1,T)work(_);
	return 0;
}
/*
3 10
10 7 13
1 1 2 5 3 9


2
3 3
1 3 5
1 1
2 2
3 3
4 4
5 5 6
2 2
2 3
3 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 73212kb

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
CABB
CCCB
CCBB

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 127ms
memory: 54876kb

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: 340ms
memory: 73516kb

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:

AAAAABBAAA
AAAABBBACA
CAAABBAACC
BBCCCAB
BBCCCCC
CCCCCCC
BCA
CCC
BCC
AAAAAA
ACAAAB
CCAAAC
BBBBBAAB
BBBBAAAA
CCCCAAAA
AAAAA
AAABC
AABBA
BBAAABBBBB
BAAAAAAAAB
CCCCCCCAAA
CCCCCCBCC
CCCCCCBCC
CCCCCAAAC
BBBCCAAABB
CCCCCAAABC
CCCCAAAAAA
ACA
BBB
BBB
BBBBBBAACB
BBBBBAAAAA
CCCBBAAACC
BCBBAABB
BBBBBABB
BBBBBB...

result:

ok ok (51263 test cases)

Test #4:

score: -100
Wrong Answer
time: 343ms
memory: 73216kb

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:

CCA
ACA
ACA
BAA
BAA
BBB
CBB
CBC
CBC
CBC
ABA
BBB
BBB
BBB
CCB
CCB
CCB
CBB
ABA
AAA
BBB
BBB
BBB
BBB
CCB
ACB
BCB
BBB
BBB
BBB
BBB
BBB
BBB
CCC
BCB
BAB
BAB
BAB
AAA
AAA
CCC
BBB
CCC
AAA
AAA
AAA
AAB
AAB
BAB
BAB
CAC
CAC
CCC
CCC
CBC
BBB
CAA
CAA
ACC
AAA
BAB
BAB
BAA
BAA
CAC
CCC
CCC
CCC
BBC
AAC
AAC
CCC
CAA
CAA
CBC
...

result:

wrong answer Pos (3,2) is not B (test case 516)