Submission #562377

#	Time	Username	Problem	Language	Result	Execution time	Memory
562377		gyegongy1	물통 (KOI17_bucket)	C++17	100 / 100	556 ms	24184 KiB

bucket

#include <cstdio>
#include <queue>
#include <map>
using namespace std;

int a, b, c, d;
struct point { int x, y, c; };

queue<point> Q;
map<pair<int, int>, int> M;

int main()
{
  //scan
  scanf("%d%d%d%d", &a, &b, &c, &d);

  //process
  Q.push({0, 0, 0});
  while(!Q.empty())
  {
    point t = Q.front(); Q.pop();
    if(t.x==c && t.y==d)
    {
      //print
      printf("%d\n", t.c);
      return 0;
    }

    if(M[{t.x, t.y}]) continue;
    M[{t.x, t.y}] = 1;

    Q.push({a, t.y, t.c+1});
    Q.push({t.x, b, t.c+1});
    Q.push({0, t.y, t.c+1});
    Q.push({t.x, 0, t.c+1});

    if(t.x<=b-t.y) Q.push({0, t.x+t.y, t.c+1});
    else Q.push({t.x-(b-t.y), b, t.c+1});

    if(t.y<=a-t.x) Q.push({t.x+t.y, 0, t.c+1});
    else Q.push({a, t.y-(a-t.x), t.c+1});
  }

  printf("-1\n");

  return 0;
}

Compilation message (stderr)

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

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