oj.uz

Submission #1099372

# Submission time Handle Problem Language Result Execution time Memory
1099372 2024-10-11T08:50:44 Z Zflop Circle Passing (EGOI24_circlepassing) C++14
31 / 100
 201 ms 13520 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()) 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:22: 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()) ans = min(ans,Do(N + bestfriend[p + 1],b) + bestfriend[p + 1] - a + 1);
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 348 KB Output is correct
2 Correct 31 ms 348 KB Output is correct
3 Correct 26 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 36 ms 744 KB Output is correct
6 Correct 33 ms 700 KB Output is correct
7 Correct 31 ms 856 KB Output is correct
8 Correct 33 ms 972 KB Output is correct
9 Correct 38 ms 952 KB Output is correct
10 Correct 34 ms 964 KB Output is correct
11 Correct 0 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 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 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 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 552 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 149 ms 11352 KB Output is correct
4 Correct 59 ms 3328 KB Output is correct
5 Correct 31 ms 844 KB Output is correct
6 Correct 32 ms 752 KB Output is correct
7 Correct 34 ms 604 KB Output is correct
8 Correct 34 ms 712 KB Output is correct
9 Correct 31 ms 752 KB Output is correct
10 Correct 31 ms 776 KB Output is correct
11 Correct 33 ms 772 KB Output is correct
12 Correct 33 ms 848 KB Output is correct
13 Correct 30 ms 800 KB Output is correct
14 Correct 33 ms 1000 KB Output is correct
15 Correct 104 ms 6084 KB Output is correct
16 Correct 98 ms 6008 KB Output is correct
17 Correct 201 ms 13520 KB Output is correct
18 Correct 187 ms 13460 KB Output is correct
19 Correct 1 ms 600 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 348 KB Output is correct
2 Correct 31 ms 348 KB Output is correct
3 Correct 26 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 36 ms 744 KB Output is correct
6 Correct 33 ms 700 KB Output is correct
7 Correct 31 ms 856 KB Output is correct
8 Correct 33 ms 972 KB Output is correct
9 Correct 38 ms 952 KB Output is correct
10 Correct 34 ms 964 KB Output is correct
11 Correct 0 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 Correct 2 ms 348 KB Output is correct
15 Incorrect 2 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -