oj.uz

Submission #1099382

# Submission time Handle Problem Language Result Execution time Memory
1099382 2024-10-11T08:54:54 Z Zflop Circle Passing (EGOI24_circlepassing) C++14
31 / 100
 207 ms 8688 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define int ll
int N,M,Q;
void solve() {
    cin >> N >> M >> Q;
    vi bestfriend{0};
    for (int i = 0; i < M;++i) {
        int b = 0;
        cin >> b;
        bestfriend.pb(b + 1);
        bestfriend.pb(b + N + 1);
        }

    auto Do = [&] (int a,int b) {
        if (a > 2 * N)
            a -= 2 * N;
        if (a > b)
            swap(a,b);
        int ans = (int)1e12;
        ans = b - a;
        ans = min(ans,a + 2 * N - b);
        return ans;
    };
    sor(bestfriend);
    while(Q--) {
        int a,b; cin >> a >> b;
        ++a,++b;
        int ans = Do(a,b);
        if(bestfriend.size() == 1) {
            cout << ans << '\n';
            continue;
        }
        int l = 1,r = bestfriend.size() - 1;
        int p = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            //cout << mid << ' ' << bestfriend[mid] << '\n';
            if (bestfriend[mid] <= a) {
                p = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(p == -1) {
            ans = min(ans,Do(bestfriend.back() - N,b) + a + 1 + 2 * N - bestfriend.back());
            ans = min(ans,Do(bestfriend[1] + N,b) + bestfriend[1] - a + 1);
        }
        if(p != -1){
            ans = min(ans,Do(N + bestfriend[p],b) + a - bestfriend[p] + 1);
            if (p + 1 == bestfriend.size()) p = 0;
            ans = min(ans,Do(N + bestfriend[p + 1],b) + bestfriend[p + 1] - a + 1);
        }
        cout << ans << "\n";
    }
}

main(){
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if (p + 1 == bestfriend.size()) p = 0;
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 348 KB Output is correct
2 Correct 32 ms 444 KB Output is correct
3 Correct 28 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 37 ms 496 KB Output is correct
6 Correct 33 ms 604 KB Output is correct
7 Correct 53 ms 596 KB Output is correct
8 Correct 32 ms 596 KB Output is correct
9 Correct 32 ms 512 KB Output is correct
10 Correct 32 ms 544 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 22.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 596 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 145 ms 8688 KB Output is correct
4 Correct 55 ms 2508 KB Output is correct
5 Correct 31 ms 532 KB Output is correct
6 Correct 30 ms 600 KB Output is correct
7 Correct 34 ms 480 KB Output is correct
8 Correct 34 ms 448 KB Output is correct
9 Correct 32 ms 600 KB Output is correct
10 Correct 44 ms 480 KB Output is correct
11 Correct 29 ms 524 KB Output is correct
12 Correct 30 ms 604 KB Output is correct
13 Correct 30 ms 596 KB Output is correct
14 Correct 31 ms 600 KB Output is correct
15 Correct 97 ms 4556 KB Output is correct
16 Correct 98 ms 4548 KB Output is correct
17 Correct 207 ms 8632 KB Output is correct
18 Correct 191 ms 8632 KB Output is correct
19 Correct 0 ms 344 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 348 KB Output is correct
2 Correct 32 ms 444 KB Output is correct
3 Correct 28 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 37 ms 496 KB Output is correct
6 Correct 33 ms 604 KB Output is correct
7 Correct 53 ms 596 KB Output is correct
8 Correct 32 ms 596 KB Output is correct
9 Correct 32 ms 512 KB Output is correct
10 Correct 32 ms 544 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 2 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -