Submission #85907

#TimeUsernameProblemLanguageResultExecution timeMemory
85907tjdgus4384물통 (KOI17_bucket)C++14
100 / 100
630 ms18704 KiB
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
set<pair<int, int> > st;

int main()
{
    int a, b, c, d;
    scanf("%d %d", &a, &b);
    scanf("%d %d", &c, &d);
    queue<pair<int, int> > q;
    q.push({0, 0});
    st.insert({0, 0});
    int ans = 0;
    while(!q.empty())
    {
        int qsize = q.size();
        for(int i = 0;i < qsize;i++)
        {
            int f = q.front().first;
            int s = q.front().second;
            q.pop();
            if(f == c && s == d)
            {
                printf("%d", ans);
                return 0;
            }
            if(!st.count({0, s})) {q.push({0, s}); st.insert({0, s});}
            if(!st.count({f, 0})) {q.push({f, 0}); st.insert({f, 0});}
            if(!st.count({a, s})) {q.push({a, s}); st.insert({a, s});}
            if(!st.count({f, b})) {q.push({f, b}); st.insert({f, b});}
            if(f + s <= a){ if(!st.count({f + s, 0})) {q.push({f + s, 0}); st.insert({f + s, 0});}}
            else if(!st.count({a, f + s - a})) {q.push({a, f + s - a}); st.insert({a, f + s - a});}
            if(f + s <= b){ if(!st.count({0, f + s})) {q.push({0, f + s}); st.insert({0, f + s});}}
            else if(!st.count({f + s - b, b})) {q.push({f + s - b, b}); st.insert({f + s - b, b});}
        }
        ans++;
    }
    printf("-1");
    return 0;
}

Compilation message (stderr)

bucket.cpp: In function 'int main()':
bucket.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~
bucket.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &c, &d);
     ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...