QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521151#5063. FillominoCrysflyWA 84ms71452kbC++174.6kb2024-08-15 22:17:072024-08-15 22:17:08

Judging History

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

  • [2024-08-15 22:17:08]
  • 评测
  • 测评结果:WA
  • 用时:84ms
  • 内存:71452kb
  • [2024-08-15 22:17:07]
  • 提交

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 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]) 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;
}

void work()
{
	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();
	--x1,--y1,--x2,--y2,--x3,--y3;
	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-abs(x-xx)) + min(abs(y-yy),m-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));
	
	a[x2][y2]=2;
	a[x3][y3]=3;
	
	priority_queue<node>q;
	q.push((node){x1,y1,dis[x1][y1],0});
	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<<"\n";
			}
		}
	}
//	cerr<<"now1 "<<now1<<"\n";
//	For(i,0,n-1){
//		For(j,0,m-1)cout<<a[i][j];
//		cout<<"\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()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*
2
3 3
1 3 5
1 1
2 2
3 3
4 4
5 5 6
2 2
2 3
3 3
*/

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 71176kb

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
CBBC
CABA
AACA
BBCC

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 84ms
memory: 71452kb

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:

CBC
CCC
ACA
BAA
AAC
AAA
ABC
BBB
BBB
CCB
CCC
CAA
CAA
AAA
ABA
BCC
BAC
AAC
BCC
CCA
BAA
ABC
ABC
BBC
AAB
BCB
BAB
ACA
BCC
BBB
CCB
BBB
BCA
ABC
ACC
AAA
ABB
AAB
BCB
BAA
AAC
AAA
BAB
BAB
CBB
BCB
BBB
ABB
AAB
CCC
CBB
BBB
ABC
ABA
BAA
BAB
BCB
BCC
ACC
AAC
BCC
AAC
AAA
CBB
CCB
ABB
AAA
BCA
ACC
BCC
ACC
CCC
BAA
AAB
BAA
...

result:

wrong answer Pos (3,1) is not C (test case 25)