oj.uz

Submission #1118135

# Submission time Handle Problem Language Result Execution time Memory
1118135 2024-11-25T02:33:28 Z Zero_OP Measures (CEOI22_measures) C++14
24 / 100
 1500 ms 5092 KB 
#include <bits/stdc++.h>

using namespace std;

void solve(vector<long long>& ar, int  D){
    if((int)ar.size() == 1){
        cout << 0 << ' ';
        return;
    }
    assert(is_sorted(ar.begin(), ar.end()));

    int N = (int)ar.size();

    long long l = 0, r = 1e18, ans = 0;
    while(l <= r){
        long long mid = l + r >> 1;
        bool ok = true;
        long long last = ar[0] - mid;
        for(int i = 1; i < N; ++i){
            if(last + D < ar[i] - mid){
                last = ar[i] - mid;
            } else if(last + D > ar[i] + mid){
                ok = false;
                break;
            } else{
                last += D;
            }
        }

        if(ok) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    if(ans & 1) cout << (ans >> 1) << ".5 ";
    else cout << (ans >> 1) << ' ';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M;
    long long D;
    cin >> N >> M >> D;

    D <<= 1;

    vector<long long> ar;
    for(int i = 1; i <= N; ++i){
        long long x; cin >> x;
        ar.push_back(x << 1);
    }

    sort(ar.begin(), ar.end());

    for(int i = 1; i <= M; ++i){
        long long x; cin >> x;
        x <<= 1;
        ar.insert(lower_bound(ar.begin(), ar.end(), x), x);
        solve(ar, D);
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void solve(std::vector<long long int>&, int)':
Main.cpp:16:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         long long mid = l + r >> 1;
      |                         ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 221 ms 5076 KB Output is correct
10 Correct 111 ms 5092 KB Output is correct
11 Correct 119 ms 5068 KB Output is correct
12 Correct 146 ms 4812 KB Output is correct
13 Correct 114 ms 4928 KB Output is correct
14 Correct 289 ms 4812 KB Output is correct
15 Correct 104 ms 4556 KB Output is correct
16 Correct 100 ms 4896 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 528 KB Time limit exceeded
2 Halted 0 ms 0 KB -