Submission #394660

#	Time	Username	Problem	Language	Result	Execution time	Memory
394660		jk410	물통 (KOI17_bucket)	C++17	100 / 100	509 ms	24200 KiB

bucket

#include <bits/stdc++.h>
using namespace std;
struct water{
    int a,b,x;
};
int a,b,c,d;
map<pair<int,int>,bool> D;
queue<water> Q;
void f(int x,int y,int v){
    if (!D[{x,y}]){
        D[{x,y}]=true;
        Q.push({x,y,v});
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>b>>c>>d;
    Q.push({0,0,0});
    D[{0,0}]=true;
    while (!Q.empty()){
        water t=Q.front();
        Q.pop();
        if (t.a==c&&t.b==d){
            cout<<t.x;
            return 0;
        }
        f(t.a,0,t.x+1);
        f(0,t.b,t.x+1);
        f(a,t.b,t.x+1);
        f(t.a,b,t.x+1);
        f(min(a,t.a+t.b),max(0,t.a+t.b-a),t.x+1);
        f(max(0,t.a+t.b-b),min(b,t.a+t.b),t.x+1);
    }
    cout<<-1;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 34 / 34
• Subtask 4: 43 / 43