QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521168 | #5063. Fillomino | Crysfly | WA | 3ms | 73320kb | C++17 | 6.3kb | 2024-08-15 23:00:22 | 2024-08-15 23:00:23 |
Judging History
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;
}
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();
--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 ;
}
if(O>=3){
if(O==20){
cout<<n<<" "<<m<<"\n";
cout<<c1<<" "<<c2<<" "<<c3<<"\n";
cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<"\n";
exit(0);
}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;
vx[y2]=vx[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]){
For(y,0,m-1) q.push((node){xx,(y1+y)%m,dis[xx][(y1+y)%m],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,dis[(x1+x)%m][yy],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()
{
int 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
*/
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 73320kb
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 2 2 1 2 1 1 0 1 1 1 0 1 2 2 1 2 AAAA CABB CCCB CCBB
result:
wrong answer Line "2 2 1 2 " doesn't correspond to pattern "[A-C]{3,500}" (test case 2)