oj.uz

Submission #1118153

# Submission time Handle Problem Language Result Execution time Memory
1118153 2024-11-25T04:38:19 Z Pannda Measures (CEOI22_measures) C++17
24 / 100
 151 ms 6784 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e6 + 5;
int n, m;
ll d, a[N], b[N];

void sub1(){
    auto check = [&](ll x) -> bool {
        b[1] = a[1] - x;
        for(int i = 2; i <= n; ++i){
            b[i] = max(b[i - 1] + d, a[i] - x);
            if(b[i] > a[i] + x) return false;
        }
        return true;
    };
    auto go = [&]() -> void {
        ll lo = 0, hi = 1e16, ans = 1e16;
        while(lo <= hi){
            ll mid = (lo + hi) / 2;
            if(check(mid)){
                ans = mid;
                hi = mid - 1;
            }
            else lo = mid + 1;
        }
        cout << ans / 2;
        if(ans & 1) cout << ".5";
        cout << " ";
    };
    while(m--){
        ll x; cin >> x;
        x *= 2;
        int pos = n + 1;
        for(int i = n; i >= 1; --i){
            if(a[i] <= x) break;
            pos = i;
        }
        for(int i = n; i >= pos; --i) a[i + 1] = a[i];
        a[pos] = x;
        ++n;
        go();
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> d;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        a[i] *= 2;
    }
    d *= 2;
    sort(a + 1, a + n + 1);
    if(m <= 10){
        sub1();
        exit(0);
    }
    return 0;
}
/**
2 1 2
1 3
2

0 5 3
1 2 3 4 5

3 3 3
3 3 3
3 3 3
**/

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 134 ms 6736 KB Output is correct
10 Correct 133 ms 6784 KB Output is correct
11 Correct 121 ms 6736 KB Output is correct
12 Correct 151 ms 6736 KB Output is correct
13 Correct 122 ms 6736 KB Output is correct
14 Correct 130 ms 6736 KB Output is correct
15 Correct 133 ms 6624 KB Output is correct
16 Correct 126 ms 6736 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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