QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521171 | #5063. Fillomino | Crysfly | WA | 407ms | 73224kb | C++17 | 6.3kb | 2024-08-15 23:02:34 | 2024-08-15 23:02:35 |
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,y,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,x,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: 100
Accepted
time: 8ms
memory: 71264kb
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 CABB CCCB CCBB
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 128ms
memory: 54780kb
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: 407ms
memory: 73224kb
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:
AAABBBBAAA AAAABBBACA AAAAACCCAA BBCCCAB BBCCCCC CCCCCCC BCA CCC BCC AAAAAA ACAAAB CCAAAC BBBBBAAB BBAAAAAA CBBAACCC AAAAA AAABC AABBA BBAAABBBBB BAAAAAAAAB CAAACCCCCC CCCCCCCCC CCCCCCBCC CCCCCAAAC CCCBBBBBAA CCCCCAAABA CCCCAAAAAA ACA BBB BBB BBBBBAAACB BBBBBAAAAA BBBCCCCCAA BCBBAABB BBBBBABB BBBBBB...
result:
wrong answer C''s size should be 4 instead of 1 (test case 1)