Submission #1118153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118153		Pannda	Measures (CEOI22_measures)	C++17	24 / 100	151 ms	6784 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41