oj.uz

Submission #58981

# Submission time Handle Problem Language Result Execution time Memory
58981 2018-07-20T01:09:33 Z andy627 None (KOI17_bucket) C++17
34 / 100
 6 ms 796 KB 
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

map<pii,int> mp;
queue<pii> q;

int main(){
    int a,b,c,d;

    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(a!=c && !c && b!=d && !d){printf("-1");return 0;}

    mp[{0,0}]=0; q.push({0,0});
    while(!q.empty()){
        int pa=q.front().ff;
        int pb=q.front().ss; q.pop();
        int pd=mp[{pa,pb}];

        if(pa==c && pb==d){printf("%d",pd);return 0;}

        if(a && mp.find({0,pb})==mp.end()) mp[{0,pb}]=pd+1,q.push({0,pb});
        if(b && mp.find({pa,0})==mp.end()) mp[{pa,0}]=pd+1,q.push({pa,0});
        if(pa!=a){
            if(mp.find({a,pb})==mp.end()) mp[{a,pb}]=pd+1,q.push({a,pb});
            if(pa+pb>a && mp.find({a,pa+pb-a})==mp.end()) mp[{a,pa+pb-a}]=pd+1,q.push({a,pa+pb-a});
            if(pa+pb<=a && mp.find({pa+pb,0})==mp.end()) mp[{pa+pb,0}]=pd+1,q.push({pa+pb,0});
        }
        if(pb!=b){
            if(mp.find({pa,b})==mp.end()) mp[{pa,b}]=pd+1,q.push({pa,b});
            if(pa+pb>b && mp.find({pa+pb-b,b})==mp.end()) mp[{pa+pb-b,b}]=pd+1,q.push({pa+pb-b,b});
            if(pa+pb<=b && mp.find({0,pa+pb})==mp.end()) mp[{0,pa+pb}]=pd+1,q.push({0,pa+pb});
        }
    }

    printf("-1");

    return 0;
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Incorrect 2 ms 496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Incorrect 2 ms 496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct
2 Correct 4 ms 564 KB Output is correct
3 Correct 3 ms 648 KB Output is correct
4 Correct 4 ms 652 KB Output is correct
5 Correct 3 ms 656 KB Output is correct
6 Correct 3 ms 660 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Correct 6 ms 796 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 6 ms 796 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Incorrect 2 ms 496 KB Output isn't correct
6 Halted 0 ms 0 KB -