QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883920 | #5063. Fillomino | Larunatrecy | WA | 210ms | 28380kb | C++14 | 6.1kb | 2025-02-05 19:53:31 | 2025-02-05 19:53:31 |
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==1200&&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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 28268kb
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: 210ms
memory: 24276kb
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
Wrong Answer
time: 5ms
memory: 28380kb
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...
result:
wrong answer C''s size should be 15 instead of 14 (test case 2)