QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884159 | #5063. Fillomino | Larunatrecy | WA | 208ms | 32456kb | C++14 | 7.5kb | 2025-02-05 21:40:23 | 2025-02-05 21:40:24 |
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],ban[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;
bool adjust(int u,int v)
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(!sig[i][j]&&a[i][j]==u&&!ban[i][j])
{
for(int k=0;k<4;k++)
{
int x=roln(i+nxt[k][0]);
int y=rolm(j+nxt[k][1]);
if(a[x][y]==v)
{
a[i][j]=v;
return 1;
}
}
}
return 0;
}
void solve()
{
++test;
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);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
a[i][j]=0;
// if(test==1&&m>3)flag=1;
// if(flag&&test<2036)return;
// if(flag)
// {
// cout<<n<<' '<<m<<endl;
// cout<<C1<<' '<<C2<<' '<<C3<<endl;
// cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<x3<<' '<<y3<<endl;
// exit(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);
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);
a[x1][y1]=1;a[x2][y2]=2;a[x3][y3]=3;
if(x2>x3)swap(x2,x3),swap(y2,y3),swap(B,C),swap(C2,C3);
int cur=C1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
sig[i][j]=a[i][j];
bool spe=0;
auto chk = [&](int c,int p)
{
if(flag)return;
if(c==1)
{
for(int j=0;j<m;j++)if(a[p][j]&&a[p][j]!=1)return;
cur--;
flag=1;
int c=0;
for(int j=0,q=y1;j<m&&cur;j++,q=rolm(q+1))
{
c++;
if(!a[p][q])a[p][q]=5,cur--;
}
if(c==m-1)
{
spe=1;
for(int i=0;i<m;i++)a[p][i]=1;
}
}
else
{
for(int j=0;j<n;j++)if(a[j][p]&&a[j][p]!=1)return;
flag=1;
cur--;
int c=0;
for(int i=0,q=x1;i<n&&cur;i++,q=roln(q+1))
{
c++;
if(!a[q][p])a[q][p]=5,cur--;
}
if(c==n-1)
{
spe=1;
for(int i=0;i<n;i++)a[i][p]=1;
}
}
};
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));
if(cur)
{
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});
}
}
while(!Q.empty())
{
auto u=Q.top();
Q.pop();
int x=u.x,y=u.y;
if(a[x][y])continue;
if(u.tp==3)
{
a[x][y]=1;
spe=1;
break;
}
}
}
else
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]==5)a[i][j]=1;
}
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++)ban[i][j]=0;
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;
}
vector<pair<int,int> > slp;
for(int k=0;k<4;k++)
{
int x=roln(nxt[k][0]),y=rolm(nxt[k][1]);
if(a[x][y]==1)slp.push_back({x,y});
}
if(slp.size()==1)
{
for(auto u:slp)
ban[u.first][u.second]=1;
}
if(spe)
{
if(adjust(1,3));
else
{
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++)
// {
// cout<<a[i][j];
// }
// cout<<endl;
// }
adjust(1,2);
}
}
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;
}
/*
1
3 6
2 14 2
3 6 2 5 3 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 30316kb
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: 208ms
memory: 28236kb
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: 109ms
memory: 30300kb
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:
AAAAABBCAA AAAAABBCCA AAAABBBCAA BCCCCAB BBCCCCC BCCCCCC BCA CCC BCC AAAACA AAAACB AAAACC BBBBBAAA BBBBBAAA CCCCAAAA AAAAA AABBC AABAA BBAAAAAABB BAAAAAAABB CCCCCCCABB CCCCCCBCC CCCCACBCC CCCCAACCC BBBCAAAABB CCCCCAAABC CCCCAAAAAC ACA BBB BBB BBBBBAAACB BBBBBBAAAA CCCBBAAACC BCBBABBB BBBBAABB BBBBBB...
result:
ok ok (51263 test cases)
Test #4:
score: -100
Wrong Answer
time: 111ms
memory: 32456kb
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:
CAC CAC BAA BAA AAA BBC BBC BBC BBB BBA BBA BCC BBC BBC CBC BBC BBC BBB BAA AAA CBB CBB CBB BBB BBB ABB CCB CBB CBB BBB BBB BBB BBB CCC BBB BBB ABA ABA AAA CAA CCC BCC BBC BAB BAB AAB AAB AAA AAA AAA ACC CCC CCC CCC BBB AAB AAC ACC ACB AAB AAB AAB AAB ACB CAC CAC AAC BAC BCC CCC CCC CCA CCA CCC CBC ...
result:
wrong answer Pos (3,2) is not A (test case 1176)