oj.uz

Submission #997484

# Submission time Handle Problem Language Result Execution time Memory
997484 2024-06-12T11:26:10 Z crafticat Measures (CEOI22_measures) C++17
35 / 100
 420 ms 17232 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll pres = 1e2;
constexpr ll inf = (1e18);
constexpr ll epsilon = 1;

ll d;
using pll = pair<ll, ll>;

set<pll> dat;

ll insert(ll x, ll cAns) {
    auto it = dat.lower_bound({x,inf});
    it--;
    auto [l, rl] = *it;
    it++;
    auto [r, rr] = *it;

    ll beg = cAns, end = inf;
    while (end > beg) {
        ll mid = beg + (end - beg) / 2;
        ll diff = mid - cAns;
        ll jump = (rl - diff + d) - x;
        if (mid == 1) {
            int stop = 25;
        }
        jump = max(jump, -mid);
        ll prev = x + jump;
        if ((rr + diff < prev + d) || jump > mid) {
            beg = mid + 1;
        } else {
            end = mid;
        }
    }
    ll mid = beg;
    ll diff = mid - cAns;
    ll jump = (rl - diff + d) - x;
    jump = max(jump, -mid);
    ll prev = x + jump;

    dat.insert({x,prev});
    return beg;
}

void printAns(ll ans) {
    cout << ans / pres;
    ans %= pres;
    if (ans != 0) cout << ".";
    ll mul = pres;
    while (ans != 0) {
        mul /= 10;
        cout << (ans / mul) % 10;
        ans %= mul;
    }
    cout << "\n";
}

int main() {
    ll n, m; cin >> n >> m >> d;
    dat.insert({-inf,-inf});
    dat.insert({inf,inf});


    ll ans = 0;
    d*=pres;
    for (ll i = 0; i < n; ++i) {
        ll x; cin >> x;
        x *= pres;
        ans = insert(x,ans);
    }


    for (ll i = 0; i < m; ++i) {
        ll x; cin >> x;
        x *= pres;
        ans = insert(x,ans);
        printAns(ans);
    }

    return 0;
}

Compilation message

Main.cpp: In function 'll insert(ll, ll)':
Main.cpp:28:17: warning: unused variable 'stop' [-Wunused-variable]
   28 |             int stop = 25;
      |                 ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 14836 KB Output is correct
2 Correct 420 ms 16976 KB Output is correct
3 Correct 415 ms 16980 KB Output is correct
4 Correct 369 ms 14932 KB Output is correct
5 Correct 386 ms 16168 KB Output is correct
6 Correct 399 ms 15332 KB Output is correct
7 Correct 383 ms 16168 KB Output is correct
8 Correct 366 ms 15236 KB Output is correct
9 Correct 342 ms 14860 KB Output is correct
10 Correct 414 ms 17232 KB Output is correct
11 Correct 394 ms 15956 KB Output is correct
12 Correct 415 ms 16800 KB Output is correct
13 Correct 370 ms 14916 KB Output is correct
14 Correct 406 ms 16844 KB Output is correct
15 Correct 408 ms 16724 KB Output is correct
16 Correct 375 ms 14672 KB Output is correct
17 Correct 417 ms 16212 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 14836 KB Output is correct
2 Correct 420 ms 16976 KB Output is correct
3 Correct 415 ms 16980 KB Output is correct
4 Correct 369 ms 14932 KB Output is correct
5 Correct 386 ms 16168 KB Output is correct
6 Correct 399 ms 15332 KB Output is correct
7 Correct 383 ms 16168 KB Output is correct
8 Correct 366 ms 15236 KB Output is correct
9 Correct 342 ms 14860 KB Output is correct
10 Correct 414 ms 17232 KB Output is correct
11 Correct 394 ms 15956 KB Output is correct
12 Correct 415 ms 16800 KB Output is correct
13 Correct 370 ms 14916 KB Output is correct
14 Correct 406 ms 16844 KB Output is correct
15 Correct 408 ms 16724 KB Output is correct
16 Correct 375 ms 14672 KB Output is correct
17 Correct 417 ms 16212 KB Output is correct
18 Incorrect 402 ms 16468 KB Output isn't correct
19 Halted 0 ms 0 KB -