oj.uz

Submission #570585

# Submission time Handle Problem Language Result Execution time Memory
570585 2022-05-30T14:49:59 Z iancu Abduction 2 (JOI17_abduction2) C++14
13 / 100
 5000 ms 394616 KB 
#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 {
  int x, y;
  int val;
  int dir;
  long long dist;

  bool operator<(const Node& n) const {
    if (val != n.val)
      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];

long long solve(int x, int y, int dir) {
  map<Node, pair<int, int>> nxt;
  int hl, hr, wl, wr;
  long long 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});
  while (!pq.empty()) {
    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 (nxt.find(n) != nxt.end()) {
      } 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;
          }
          nxt[n] = {hl, n.y};
      }
      pq.push({nxt[n].first, nxt[n].second, a[nxt[n].first], WEST, n.dist + n.x - nxt[n].first});
      pq.push({nxt[n].first, nxt[n].second, a[nxt[n].first], EAST, n.dist + n.x - nxt[n].first});
    } else if (n.dir == SOUTH) {
      if (nxt.find(n) == nxt.end()) {
        while (hr < h && a[hr] <= b[n.y])
          ++hr;
        if (a[hr] <= b[n.y]) {
          ans = max(ans, n.dist + hr - n.x);
          continue;
        }
        nxt[n] = {hr, n.y};
      }
      pq.push({nxt[n].first, nxt[n].second, a[nxt[n].first], WEST, n.dist + nxt[n].first - n.x});
      pq.push({nxt[n].first, nxt[n].second, a[nxt[n].first], EAST, n.dist + nxt[n].first - n.x});
    } else if (n.dir == EAST) {
      if (nxt.find(n) == nxt.end()) {
        while (wr < w && b[wr] <= a[n.x])
          ++wr;
        if (b[wr] <= a[n.x]) {
          ans = max(ans, n.dist + wr - n.y);
          continue;
        }
        nxt[n] = {n.x, wr};
      }
      pq.push({nxt[n].first, nxt[n].second, b[nxt[n].second], NORTH, n.dist + nxt[n].second - n.y});
      pq.push({nxt[n].first, nxt[n].second, b[nxt[n].second], SOUTH, n.dist + nxt[n].second - n.y});
    } else {
      if (nxt.find(n) == nxt.end()) {
        while (wl > 1 && b[wl] <= a[n.x])
          --wl;
        if (b[wl] <= a[n.x]) {
          ans = max(ans, n.dist + n.y - wl);
          continue;
        }
        nxt[n] = {n.x, wl};
      }
      pq.push({nxt[n].first, nxt[n].second, b[nxt[n].second], NORTH, n.dist + n.y - nxt[n].second});
      pq.push({nxt[n].first, nxt[n].second, b[nxt[n].second], SOUTH, n.dist + n.y - nxt[n].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;
    long long ans = 0;
    for (int i = 0; i < 4; ++i)
      ans = max(ans, solve(x, y, i));
    cout << ans << "\n";
  }
  return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 5053 ms 394468 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 5053 ms 394468 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1020 KB Output is correct
2 Correct 76 ms 664 KB Output is correct
3 Correct 97 ms 1228 KB Output is correct
4 Correct 132 ms 1116 KB Output is correct
5 Correct 118 ms 1692 KB Output is correct
6 Correct 108 ms 588 KB Output is correct
7 Correct 106 ms 516 KB Output is correct
8 Execution timed out 5067 ms 394616 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 5053 ms 394468 KB Time limit exceeded
20 Halted 0 ms 0 KB -