結果
| 問題 | No.3749 Three Jugs |
| コンテスト | |
| ユーザー |
 Naru820
|
| 提出日時 | 2026-09-23 21:45:52 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,284 ms / 5,000 ms |
| + 95µs | |
| コード長 | 9,316 bytes |
| 記録 | |
| コンパイル時間 | 3,133 ms |
| コンパイル使用メモリ | 365,388 KB |
| 実行使用メモリ | 7,856 KB |
| 最終ジャッジ日時 | 2026-09-25 20:56:34 |
| 合計ジャッジ時間 | 12,854 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 23 |
コンパイルメッセージ
main.cpp: In function 'Res run(Sys&, int, ll, int, ll)':
main.cpp:103:51: warning: 'cz' may be used uninitialized [-Wmaybe-uninitialized]
103 | if(s.z>u)H(tau+cu-(s.o+cz),s.lab);
| ~~~~^~~~
main.cpp:101:30: note: 'cz' was declared here
101 | i128 cz,zf=push(s.z,cz);
| ^~
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef __int128 i128; typedef array<ll,3> P3;
struct Piece{ i128 a,b,s,c; };
struct Stop{ i128 z,o; int lab; };
struct Res{ bool ok=false; i128 time=0; int lab=0; };
struct Sys{
ll A[3],S,lo[3],hi[3]; i128 off[6],L;
void init(const ll*AA,ll SS){
for(int i=0;i<3;i++)A[i]=AA[i]; S=SS;
for(int k=0;k<3;k++){lo[k]=max(0LL,S-A[(k+1)%3]-A[(k+2)%3]);hi[k]=min(A[k],S);}
i128 p=0;
for(int k=0;k<3;k++)for(int j=0;j<2;j++){
if(hi[k]-lo[k]>0){off[k*2+j]=p;p+=hi[k]-lo[k];} else off[k*2+j]=-1;}
L=p;
}
i128 pos(int k,int sg,i128 v){return off[k*2+(sg==1?0:1)]+(sg==1?v-lo[k]:hi[k]-v);}
};
Res better(const Res&x,const Res&y){
if(!x.ok)return y; if(!y.ok)return x;
if(x.time!=y.time)return x.time<y.time?x:y;
return x.lab==-1?x:y;
}
Res run(Sys&sy,int sk,ll sv,int tk,ll tv){
vector<Piece> pc; vector<Stop> st; ll S=sy.S;
for(int k=0;k<3;k++)for(int j=0;j<2;j++){
int sg=j==0?1:-1; if(sy.off[k*2+j]<0)continue;
i128 o=sy.off[k*2+j]; ll lo=sy.lo[k],hi=sy.hi[k]; i128 ln=hi-lo;
ll t=S-sy.A[(k+2)%3], tc=min(max(t,lo),hi); int k1=(k+1)%3,k2=(k+2)%3;
i128 ra0,ra1,rb0,rb1; ll vA,vB;
if(sg==1){ra0=o;ra1=o+(tc-lo);rb0=ra1;rb1=o+ln;vA=lo;vB=tc;}
else{rb0=o;rb1=o+(hi-tc);ra0=rb1;ra1=o+ln;vA=tc;vB=hi;}
if(ra1>ra0)pc.push_back({ra0,ra1,sy.pos(k1,-sg,(i128)t-vA)-sy.pos(k,sg,vA),1});
if(rb1>rb0)pc.push_back({rb0,rb1,sy.pos(k2,-sg,(i128)S-vB)-sy.pos(k,sg,vB),1});
if(lo<t&&t<hi)st.push_back({sy.pos(k,sg,t),0,k});
}
i128 u=sy.pos(sk,1,sv),tau=0;
if(tk>=0){st.push_back({sy.pos(tk,1,tv),0,-1});st.push_back({sy.pos(tk,-1,tv),0,-1});}
for(auto&s:st)if(s.z==u&&s.lab>=0){Res r;r.ok=true;r.lab=s.lab;return r;}
Res best; vector<pair<i128,int>> dropped; bool haveP=false; i128 P=0;
auto H=[&](i128 t,int lab){Res r;r.ok=true;r.time=t;r.lab=lab;best=better(best,r);};
i128 lam=sy.L;
while(lam>0){
if(st.empty()&&(dropped.empty()||haveP))break;
int ai=-1,bi=-1;
for(int i=0;i<(int)pc.size();i++){if(pc[i].b==lam)ai=i;if(pc[i].b+pc[i].s==lam)bi=i;}
i128 la=pc[ai].b-pc[ai].a, lb=pc[bi].b-pc[bi].a;
if(ai==bi){
if(pc[ai].a<=u){haveP=true;P=pc[ai].c;break;}
i128 a0=pc[ai].a; vector<Stop> ns; for(auto&s:st)if(s.z<a0)ns.push_back(s); st=ns;
pc.erase(pc.begin()+ai); lam=a0; continue;
}
vector<Stop> ns;
if(la>lb){
Piece al=pc[ai]; i128 aend=al.b+al.s,LR=0;
for(auto&q:pc)if(q.a+q.s>=aend)LR+=q.b-q.a;
i128 q=(la-1)/LR, ca=al.c;
if(q>=1){
i128 nl=lam-q*LR, step=LR;
auto push=[&](i128 z,i128&m){m=(z-nl)/step+1;return z-m*step;};
bool uc=u>=nl; i128 uf=0,mu=0; if(uc)uf=push(u,mu);
for(auto&s:st){
if(s.z>=nl){
i128 mz,zf=push(s.z,mz);
if(uc&&((u-s.z)%step+step)%step==0){
if(s.z<u)H(tau+((u-s.z)/step)*ca-s.o,s.lab);
else dropped.push_back({tau-(s.o+((s.z-u)/step)*ca),s.lab});
continue;}
if(!uc&&zf==u){dropped.push_back({tau-(s.o+mz*ca),s.lab});continue;}
ns.push_back({zf,s.o+mz*ca,s.lab});
} else { if(uc&&s.z==uf){H(tau+mu*ca-s.o,s.lab);continue;} ns.push_back(s); }
}
if(uc){u=uf;tau+=mu*ca;}
pc[ai].b=nl;
for(auto&p:pc)if(p.a+p.s>=aend){p.s-=q*LR;p.c+=q*ca;}
lam=nl;
} else {
i128 nl=lam-lb, sa=al.s; bool uc=u>=nl; i128 uf=u+sa;
for(auto&s:st){
if(s.z>=nl){ i128 zf=s.z+sa;
if(!uc&&zf==u){dropped.push_back({tau-(s.o+ca),s.lab});continue;}
ns.push_back({zf,s.o+ca,s.lab});
} else { if(uc&&s.z==uf){H(tau+ca-s.o,s.lab);continue;} ns.push_back(s); }
}
if(uc){u=uf;tau+=ca;}
pc[ai].b=nl; pc[bi].s+=sa; pc[bi].c+=ca; lam=nl;
}
} else {
i128 bend=pc[bi].b,LD=0; vector<int> D;
for(int i=0;i<(int)pc.size();i++)if(pc[i].a>=bend){D.push_back(i);LD+=pc[i].b-pc[i].a;}
i128 q=la<lb?(lb-1)/LD:0;
if(q>=1){
i128 nl=lam-q*LD, cb=pc[bi].c;
auto push=[&](i128 z,i128&cost){
i128 m=z>=lam-LD?0:(lam-LD-z+LD-1)/LD, x=z+m*LD;
for(int i:D)if(pc[i].a<=x&&x<pc[i].b){cost=m*cb+pc[i].c;return x+pc[i].s;}
return (i128)0;};
bool uc=u>=nl; i128 uf=0,cu=0; if(uc)uf=push(u,cu);
for(auto&s:st){
if(s.z>=nl){
i128 cz,zf=push(s.z,cz);
if(uc&&zf==uf){
if(s.z>u)H(tau+cu-(s.o+cz),s.lab);
else dropped.push_back({tau+cu-(s.o+cz),s.lab});
continue;}
if(!uc&&zf==u){dropped.push_back({tau-(s.o+cz),s.lab});continue;}
ns.push_back({zf,s.o+cz,s.lab});
} else { if(uc&&s.z==uf){H(tau+cu-s.o,s.lab);continue;} ns.push_back(s); }
}
if(uc){u=uf;tau+=cu;}
pc[bi].b-=q*LD;
for(int i:D){pc[i].a-=q*LD;pc[i].b-=q*LD;pc[i].s+=q*LD;pc[i].c+=q*cb;}
lam=nl;
} else {
Piece al=pc[ai]; i128 nl=lam-la, sa=al.s, ca=al.c; bool uc=u>=nl; i128 uf=u+sa;
for(auto&s:st){
if(s.z>=nl){ i128 zf=s.z+sa;
if(!uc&&zf==u){dropped.push_back({tau-(s.o+ca),s.lab});continue;}
ns.push_back({zf,s.o+ca,s.lab});
} else { if(uc&&s.z==uf){H(tau+ca-s.o,s.lab);continue;} ns.push_back(s); }
}
if(uc){u=uf;tau+=ca;}
if(la==lb){pc[bi].s+=sa;pc[bi].c+=ca;pc.erase(pc.begin()+ai);}
else{ Piece b2{pc[bi].b-la,pc[bi].b,pc[bi].s+sa,pc[bi].c+ca};
pc[bi].b-=la; pc.erase(pc.begin()+ai); pc.push_back(b2); }
lam=nl;
}
}
st=ns;
}
if(haveP)for(auto&d:dropped)H(P+d.first,d.second);
return best;
}
P3 perm(const P3&x){return {x[0],x[2],x[1]};}
int nextra(const P3&A,const P3&p){int c=0;for(int i=0;i<3;i++)if(p[i]==0||p[i]==A[i])c++;return c;}
pair<int,ll> fstate(const P3&A,const P3&p){
for(int t=0;t<3;t++){
if(p[t]==0){int k=(t+1)%3;return {k,p[k]};}
if(p[t]==A[t]){int k=(t+2)%3;return {k,p[k]};}
}
return {-1,0};
}
ll solve(P3 A,P3 B,P3 C){
if(B==C)return 0;
int ex=nextra(A,C); if(ex==0)return -1;
ll S=B[0]+B[1]+B[2];
map<P3,int> dist; deque<P3> dq; dist[B]=0; dq.push_back(B);
while(!dq.empty()){
P3 p=dq.front();dq.pop_front(); int d=dist[p]; if(d>=7)continue;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(i!=j){
ll m=min(p[i],A[j]-p[j]); if(m<=0)continue;
P3 q=p; q[i]-=m; q[j]+=m;
if(!dist.count(q)){dist[q]=d+1;dq.push_back(q);}
}
}
const i128 INF=(i128)1<<120; i128 best=INF;
if(dist.count(C))best=dist[C];
if(ex>=2)return best==INF?-1:(ll)best;
P3 Ap=perm(A); Sys sy,sr; sy.init(A.data(),S); sr.init(Ap.data(),S);
auto sC=fstate(A,C); auto sCr=fstate(Ap,perm(C));
for(int r=0;r<2;r++){
Sys&y=r?sr:sy; auto s=r?sCr:sC; const P3&AA=r?Ap:A;
Res res=run(y,s.first,s.second,-1,0);
if(res.ok&&res.lab>=0){
int k=res.lab; P3 V; V[k]=S-AA[(k+2)%3]; V[(k+2)%3]=AA[(k+2)%3]; V[(k+1)%3]=0;
if(r)V=perm(V);
if(dist.count(V))best=min(best,(i128)dist[V]+res.time+1);
}
}
int exB=nextra(A,B);
if(exB==1){
auto sB=fstate(A,B); Res r1=run(sy,sB.first,sB.second,sC.first,sC.second);
if(r1.ok&&r1.lab==-1)best=min(best,r1.time);
auto sBr=fstate(Ap,perm(B)); Res r2=run(sr,sBr.first,sBr.second,sCr.first,sCr.second);
if(r2.ok&&r2.lab==-1)best=min(best,r2.time);
} else if(exB==0){
for(int k=0;k<3;k++){
if(!(k==sC.first&&B[k]==sC.second)){
Res r1=run(sy,k,B[k],sC.first,sC.second);
if(r1.ok&&r1.lab==-1)best=min(best,r1.time);
}
ll w=S-B[k]; P3 Pp; Pp[k]=B[k]; Pp[(k+1)%3]=min(A[(k+1)%3],w); Pp[(k+2)%3]=w-Pp[(k+1)%3];
if(Pp==C)best=min(best,(i128)1);
else if(nextra(A,Pp)==1){
auto sp=fstate(Ap,perm(Pp)); Res r2=run(sr,sp.first,sp.second,sCr.first,sCr.second);
if(r2.ok&&r2.lab==-1)best=min(best,1+r2.time);
}
}
}
return best==INF?-1:(ll)best;
}
int main(){
int T; if(scanf("%d",&T)!=1)return 0; string out;
while(T--){
P3 A,B,C;
for(auto&x:A)if(scanf("%lld",&x)!=1)return 0;
for(auto&x:B)if(scanf("%lld",&x)!=1)return 0;
for(auto&x:C)if(scanf("%lld",&x)!=1)return 0;
out+=to_string(solve(A,B,C)); out+='\n';
}
fputs(out.c_str(),stdout);
}