Submission #1082047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082047		vjudge1	Measures (CEOI22_measures)	C++17	0 / 100	1537 ms	3800 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()

const int mxn = 2e5 + 100;

int n, m, d;
vector<ll> v(mxn);
ld ans = 0;

pair<ld, pair<ld, ld>> calc(vector<pair<ld, ld>> cur, vector<ld> dist) {
    // cout << cur.size() << endl;
    // for (auto x : cur) cout << x.first << " " << x.second << endl;
    // cout << endl;
    if (cur.size() <= 1) return {cur[0].first, {cur[0].second, dist[0]}};
    int mid = cur.size() / 2;
    bool odd = (cur.size() % 2);
    int r = mid + 1;
    ld MX = 0;
    if (odd) mid--;
    if (!odd) {
        mid--;
        r--;
        ld D = cur[r].first - cur[mid].second;
        ld total = d - D;
        dist[mid] += total / 2;
        dist[r] += total / 2;
        MX = max(MX, dist[mid]);
        MX = max(MX, dist[r]);
        ans = max(ans, dist[mid]);
        ans = max(ans, dist[r]);
        cur[mid].first -= total / 2;
        cur[mid].second -= total / 2;
        cur[r].first += total / 2;
        cur[r].second += total / 2;
        r++;
        mid--;
    }
    // cout << "! " << mid << " " << r << endl;
    for (int i = mid; i >= 0 && r < cur.size(); i--) {
        ld D = cur[r].first - cur[r - 1].second;
        ld total = d - D;
        dist[r] += total;
        MX = max(MX, dist[r]);
        ans = max(ans, dist[r]);
        cur[r].first += total;
        cur[r].second += total;

        D = cur[i + 1].first - cur[i].second;
        total = d - D;
        dist[i] += total;
        MX = max(MX, dist[i]);
        ans = max(ans, dist[i]);
        cur[i].first -= total;
        cur[i].second -= total;
        r++;
    }
    // cout << cur[0].first << " " << cur[cur.size() - 1].second << " " << MX << endl;
    return {cur[0].first, {cur[cur.size() - 1].second, MX}};
}

void solve(vector<pair<ld, ld>> cur, vector<ld> dist) {
    if (cur.size() <= 1) return;
    vector<pair<ld, ld>> groups;
    vector<ld> mx;
    int start = 0, sz = 1;
    ld MX = dist[0];
    bool good = 1;
    for (int i = 0; i < cur.size() - 1; i++) {
        if (abs(cur[i + 1].first - cur[i].second) < d) {
            good = 0;
            sz++;
            MX = max(MX, dist[i]);
        }
        else {
            groups.push_back({start, start + sz - 1});
            mx.push_back(MX);
            MX = dist[i + 1];
            start = i + 1;
            sz = 1;
        }
    }
    if (good) return;
    groups.push_back({start, start + sz - 1});
    mx.push_back(MX);
    vector<pair<ld, ld>> newC;
    vector<ld> newD;
    for (auto x : groups) {
        vector<pair<ld, ld>> v;
        vector<ld> D;
        for (int i = x.first; i <= x.second; i++) v.push_back({cur[i]}), D.push_back(dist[i]);
        pair<ld, pair<ld, ld>> get = calc(v, D);
        newC.push_back({get.first, get.second.first});
        newD.push_back(get.second.second);
    }
    solve(newC, newD);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> d;
    v.resize(n);
    vector<pair<ld, ld>> rn;
    vector<ld> dist;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        rn.push_back({v[i], v[i]});
        dist.push_back(0);
    }
    for (int i = 0; i < m; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
        rn.push_back({x, x});
        sort(all(rn));
        dist.push_back(0);
        n++;
        ans = 0;
        solve(rn, dist);
        cout << ans << " "; 
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::pair<long double, std::pair<long double, long double> > calc(std::vector<std::pair<long double, long double> >, std::vector<long double>)':
Main.cpp:45:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = mid; i >= 0 && r < cur.size(); i--) {
      |                                 ~~^~~~~~~~~~~~
Main.cpp: In function 'void solve(std::vector<std::pair<long double, long double> >, std::vector<long double>)':
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < cur.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41