QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884002 | #5063. Fillomino | Larunatrecy | WA | 209ms | 32460kb | C++14 | 6.4kb | 2025-02-05 20:42:39 | 2025-02-05 20:42:40 |
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()
{
++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<22)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;
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;
for(int j=0,q=y1;j<m&&cur;j++,q=rolm(q+1))
{
if(!a[p][q])a[p][q]=5,cur--;
}
}
else
{
for(int j=0;j<n;j++)if(a[j][p]&&a[j][p]!=1)return;
flag=1;
cur--;
for(int i=0,q=x1;i<n&&cur;i++,q=roln(q+1))
{
if(!a[q][p])a[q][p]=5,cur--;
if(!cur)break;
}
}
};
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;
// }
if(cur)
{
// 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});
}
}
}
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++)
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: 3ms
memory: 32460kb
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: 209ms
memory: 24272kb
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: 107ms
memory: 30416kb
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:
wrong answer C''s size should be 7 instead of 6 (test case 995)