oj.uz

Submission #1098339

# Submission time Handle Problem Language Result Execution time Memory
1098339 2024-10-09T10:11:12 Z ALTAKEXE Circle Passing (EGOI24_circlepassing) C++17
20 / 100
 31 ms 32196 KB 
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
int best[4000002], r[4000002], l[4000002];
int n, m, q;
int dist(int a, int b)
{
  return min(abs(a - b), 2 * n - abs(a - b));
}
int main()
{
  cin >> n >> m >> q;
  for (int i = 0; i < n * 2; i++)
    best[i] = 0;
  for (int i = 0; i < m; i++)
  {
    int x;
    cin >> x;
    best[x] = best[x + n] = 1;
  }
  int po = -1;
  for (int i = 0; i < n * 3; i++)
  {
    if (best[i % (n * 2)])
      po = i % (n * 2);
    l[i % (n * 2)] = po;
  }
  po = -1;
  for (int i = n * 3 - 1; i >= 0; i--)
  {
    if (best[i % (n * 2)])
      po = i % (n * 2);
    r[i % (n * 2)] = po;
  }
  while (q--)
  {
    int a, b;
    cin >> a >> b;
    if (a > b)
      swap(a, b);
    int m1 = dist(a, b);
    int m2 = l[a] == -1 ? 1e9 : dist(a, l[a]) + dist((l[a] + n) % (n * 2), b) + 1;
    int m3 = r[a] == -1 ? 1e9 : dist(a, r[a]) + dist((r[a] + n) % (n * 2), b) + 1;
    // cout << m1 << " " << m2 << " " << m3 << " " << left[a] << " " << right[a] << " m\n";
    cout << min(min(m1, m2), m3) << "\n";
  }
  return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB Output is correct
2 Correct 25 ms 348 KB Output is correct
3 Correct 27 ms 476 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 31 ms 2908 KB Output is correct
6 Runtime error 23 ms 32088 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 2 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Correct 2 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Runtime error 22 ms 32196 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 32104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB Output is correct
2 Correct 25 ms 348 KB Output is correct
3 Correct 27 ms 476 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 31 ms 2908 KB Output is correct
6 Runtime error 23 ms 32088 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -