QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883921 | #5063. Fillomino | Larunatrecy | TL | 211ms | 30432kb | C++14 | 6.1kb | 2025-02-05 19:54:35 | 2025-02-05 19:54:36 |
Judging History
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&°[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()
{
int C1,C2,C3,x1,y1,x2,y2,x3,y3;
read(n);read(m);
if(test==0&&m>3)flag=1;
read(C1);read(C2);read(C3);
read(x1);read(y1);read(x2);read(y2);read(x3);read(y3);
++test;
if(test==1350&&flag)exit(0);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
a[i][j]=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);
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
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 30432kb
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: 211ms
memory: 26324kb
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
Time Limit Exceeded
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:
AAAAABAAAA AAAAABBBCA CAAABBABCC BCCACAB BBCCCCC BCCCCCC BCA CCC BCC AAAACC AAAAAB AAAABC BBBBBAAA CBBBBAAA CCCCBAAA AAAAA AABBC AABAA BBAAAAAABB CAAAAAAABB CBCCCCCBBC CCCCCCCBC CCCCACBCC CCCCAACCC BBCBAAAABB CCCCCAAABC CCCCAABAAC ACA BBB BBB BBBBBBCACB BBBBBAAAAA CBCCBAAACC BCCBBABB BBBBBABB BBBBBB...