oj.uz

Submission #1048264

# Submission time Handle Problem Language Result Execution time Memory
1048264 2024-08-08T06:08:10 Z 정민찬(#11037) Circle Passing (EGOI24_circlepassing) C++17
14 / 100
 55 ms 8804 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll N, M, Q;

ll dist(ll x, ll y) {
    return min((x - y + 2*N) % (2*N), (y - x + 2*N) % (2*N));
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    
    cin >> N >> M >> Q;
    vector<ll> bst;
    for (ll i=0; i<M; i++) {
        ll t;
        cin >> t;
        bst.push_back(t);
        bst.push_back(t+N);
    }
    sort(bst.begin(), bst.end());
    while (Q --) {
        ll u, v;
        cin >> u >> v;
        ll idx1 = lower_bound(bst.begin(), bst.end(), u) - bst.begin() + 1;
        idx1 %= bst.size();
        ll idx2 = (idx1 - 1 + bst.size()) % bst.size();
        ll ans = dist(u, v);
        ans = min(ans, dist(u,bst[idx1]) + 1 + dist((bst[idx1]+N)%(2*N), v));
        ans = min(ans, dist(u,bst[idx2]) + 1 + dist((bst[idx2]+N)%(2*N), v));
        cout << ans << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 0 ms 372 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 624 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 360 KB Output is correct

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 22.0

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

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 55 ms 8804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 0 ms 372 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 624 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 360 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -