Submission #572934

#	Time	Username	Problem	Language	Result	Execution time	Memory
572934		iancu	Abduction 2 (JOI17_abduction2)	C++14	40 / 100	279 ms	1908 KiB

abduction2

#include <bits/stdc++.h>

#define NORTH 0
#define SOUTH 1
#define EAST  2
#define WEST  3

using namespace std;

const int N = 5e4 + 5;

struct Node {
  unsigned short x, y;
  int val;
  char dir;
  int dist;

  bool operator<(const Node& n) const {
    return val > n.val;
    //return make_tuple(x, y, dir) < make_tuple(n.x, n.y, n.dir);
  }
};

int h, w;
int a[N], b[N];

vector<unsigned short> nxt0(N, 0);
vector<unsigned short> nxt1(N, 0);
vector<unsigned short> nxt2(N, 0);
vector<unsigned short> nxt3(N, 0);
vector<int> dp1sus(N, 0);
vector<int> dp1jos(N, 0);
vector<int> dp2st(N, 0);
vector<int> dp2dr(N, 0);

int solve(int x, int y, int dir) {
  fill(nxt0.begin(), nxt0.begin() + max(h, w) + 2, 0);
  fill(nxt1.begin(), nxt1.begin() + max(h, w) + 2, 0);
  fill(nxt2.begin(), nxt2.begin() + max(h, w) + 2, 0);
  fill(nxt3.begin(), nxt3.begin() + max(h, w) + 2, 0);
  fill(dp1sus.begin(), dp1sus.begin() + max(h, w) + 2, 0);
  fill(dp1jos.begin(), dp1jos.begin() + max(h, w) + 2, 0);
  fill(dp2st.begin(), dp2st.begin() + max(h, w) + 2, 0);
  fill(dp2dr.begin(), dp2dr.begin() + max(h, w) + 2, 0);
  int hl, hr, wl, wr;
  int ans = 0;
  hl = hr = x;
  wl = wr = y;
  if (dir == 0) hl = max(hl - 1, 1);
  else if (dir == 1) hr = min(hr + 1, h);
  else if (dir == 2) wr = min(wr + 1, w);
  else wl = max(wl - 1, 1);
  priority_queue<Node> pq;
  pq.push({x, y, 0, dir, 0});

  int pasi = 0;

  while (!pq.empty() && pasi < 8 * (w + h + 1)) {
      ++pasi;
    auto n = pq.top();
    //cout << n.x << " " << n.y << " " << n.dir << " " << n.dist << endl;
    pq.pop();
    ans = max(ans, n.dist);

    if (n.dir == NORTH && n.x == 1)
      continue;
    if (n.dir == SOUTH && n.x == h)
      continue;
    if (n.dir == EAST  && n.y == w)
      continue;
    if (n.dir == WEST  && n.y == 1)
      continue;

    if (n.dir == NORTH) {
      if (nxt0[n.y] != 0) {
      } else {
          while (hl > 1 && a[hl] <= b[n.y])
            --hl;
          if (a[hl] <= b[n.y]) {
            ans = max(ans, n.dist + n.x - hl);
            continue;
          }
          nxt0[n.y] = hl;
      }
      pair<int, int> urm = {nxt0[n.y], n.y};
      if (dp1sus[n.y] >= n.dist + n.x - urm.first)
        continue;
      dp1sus[n.y] = n.dist + n.x - urm.first;
      pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + n.x - urm.first});
      pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + n.x - urm.first});
    } else if (n.dir == SOUTH) {
      if (nxt1[n.y] == 0) {
        while (hr < h && a[hr] <= b[n.y])
          ++hr;
        if (a[hr] <= b[n.y]) {
          ans = max(ans, n.dist + hr - n.x);
          continue;
        }
        nxt1[n.y] = hr;
      }
      pair<int, int> urm = {nxt1[n.y], n.y};
      if (dp1jos[n.y] >= n.dist + urm.first - n.x)
        continue;
      dp1jos[n.y] = n.dist + urm.first - n.x;
      pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + urm.first - n.x});
      pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + urm.first - n.x});
    } else if (n.dir == EAST) {
      if (nxt2[n.x] == 0) {
        while (wr < w && b[wr] <= a[n.x])
          ++wr;
        if (b[wr] <= a[n.x]) {
          ans = max(ans, n.dist + wr - n.y);
          continue;
        }
        nxt2[n.x] = wr;
      }
      pair<int, int> urm = {n.x, nxt2[n.x]};
      if (dp2dr[n.x] >= n.dist + urm.second - n.y)
        continue;
      dp2dr[n.x] = n.dist + urm.second - n.y;
      pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + urm.second - n.y});
      pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + urm.second - n.y});
    } else {
      if (nxt3[n.x] == 0) {
        while (wl > 1 && b[wl] <= a[n.x])
          --wl;
        if (b[wl] <= a[n.x]) {
          ans = max(ans, n.dist + n.y - wl);
          continue;
        }
        nxt3[n.x] = wl;
      }
      pair<int, int> urm = {n.x, nxt3[n.x]};
      if (dp2st[n.x] >= n.dist + n.y - urm.second)
        continue;
      dp2st[n.x] = n.dist + n.y - urm.second;
      pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + n.y - urm.second});
      pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + n.y - urm.second});
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int q;
  cin >> h >> w >> q;
  for (int i = 1; i <= h; ++i)
    cin >> a[i];
  for (int i = 1; i <= w; ++i)
    cin >> b[i];
  while (q--) {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    for (int i = 0; i < 4; ++i)
      ans = max(ans, solve(x, y, i));
    cout << ans << "\n";
  }
  return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int solve(int, int, int)':
abduction2.cpp:54:12: warning: narrowing conversion of 'x' from 'int' to 'short unsigned int' [-Wnarrowing]
   54 |   pq.push({x, y, 0, dir, 0});
      |            ^
abduction2.cpp:54:15: warning: narrowing conversion of 'y' from 'int' to 'short unsigned int' [-Wnarrowing]
   54 |   pq.push({x, y, 0, dir, 0});
      |               ^
abduction2.cpp:54:21: warning: narrowing conversion of 'dir' from 'int' to 'char' [-Wnarrowing]
   54 |   pq.push({x, y, 0, dir, 0});
      |                     ^~~
abduction2.cpp:89:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
   89 |       pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + n.x - urm.first});
      |                ~~~~^~~~~
abduction2.cpp:89:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
   89 |       pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + n.x - urm.first});
      |                           ~~~~^~~~~~
abduction2.cpp:90:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
   90 |       pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + n.x - urm.first});
      |                ~~~~^~~~~
abduction2.cpp:90:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
   90 |       pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + n.x - urm.first});
      |                           ~~~~^~~~~~
abduction2.cpp:105:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  105 |       pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + urm.first - n.x});
      |                ~~~~^~~~~
abduction2.cpp:105:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  105 |       pq.push({urm.first, urm.second, a[urm.first], WEST, n.dist + urm.first - n.x});
      |                           ~~~~^~~~~~
abduction2.cpp:106:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  106 |       pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + urm.first - n.x});
      |                ~~~~^~~~~
abduction2.cpp:106:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  106 |       pq.push({urm.first, urm.second, a[urm.first], EAST, n.dist + urm.first - n.x});
      |                           ~~~~^~~~~~
abduction2.cpp:121:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  121 |       pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + urm.second - n.y});
      |                ~~~~^~~~~
abduction2.cpp:121:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  121 |       pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + urm.second - n.y});
      |                           ~~~~^~~~~~
abduction2.cpp:122:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  122 |       pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + urm.second - n.y});
      |                ~~~~^~~~~
abduction2.cpp:122:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  122 |       pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + urm.second - n.y});
      |                           ~~~~^~~~~~
abduction2.cpp:137:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  137 |       pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + n.y - urm.second});
      |                ~~~~^~~~~
abduction2.cpp:137:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  137 |       pq.push({urm.first, urm.second, b[urm.second], NORTH, n.dist + n.y - urm.second});
      |                           ~~~~^~~~~~
abduction2.cpp:138:20: warning: narrowing conversion of 'urm.std::pair<int, int>::first' from 'int' to 'short unsigned int' [-Wnarrowing]
  138 |       pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + n.y - urm.second});
      |                ~~~~^~~~~
abduction2.cpp:138:31: warning: narrowing conversion of 'urm.std::pair<int, int>::second' from 'int' to 'short unsigned int' [-Wnarrowing]
  138 |       pq.push({urm.first, urm.second, b[urm.second], SOUTH, n.dist + n.y - urm.second});
      |                           ~~~~^~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56