oj.uz

Submission #1100597

# Submission time Handle Problem Language Result Execution time Memory
1100597 2024-10-14T09:46:36 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 951 ms 12832 KB 
#include <bits/stdc++.h>

using ll = long long;
using namespace std;
template<typename T>

using V = vector<T>;
using vi = V<ll>;
using vb = V<bool>;
using pi = pair<ll,ll>;


vi water, flowers;
V<bool> types;
set<ll> problems;
constexpr ll inf = 1e9 * 2 + 7;

bool between(ll l, ll r) {
    auto it = problems.upper_bound(l);
    if (it == problems.end() || *it >= r) return true;
    return false;
}

ll pos(V<V<ll>> &dp, ll i, ll lastR, ll r) {
    ll leftR = -1;
    if (i >= 0) {
        for (ll j = 0; j < 3; ++j) {
            if (j == 0) leftR = water[i];
            if (j == 1 && i - 1 >= 0) leftR = water[i - 1] + r;
            if (j == 2) leftR = water[i] + r;
            if (dp[i][j] == -1) continue;
            if (between(leftR, lastR)) return j;
        }
    } else {
       return between(0, lastR) ? 0 : -1;
    }
    return -1;
}

bool ok(ll r) {
    V<V<ll>> dp(water.size() + 1, vi(3,-1));

    for (ll i = 0; i < water.size(); ++i) {
        for (ll j = 0; j < 3; ++j) {
            ll lastR = -1;
            if (j == 0) lastR = water[i] - r;
            if (j == 1 && between(water[i - 1] + r, water[i] - r)) lastR = water[i] - r;
            if (j == 2) lastR = water[i];
            dp[i][j] = pos(dp,i - 1 + (j == 1 ? -1 : 0),lastR, r);
        }
    }

    // Backtrace
    ll last = dp[water.size() - 1][2];
    ll i = water.size() - 1;
    if (last == -1) return false;
    while (last != -1) {
        if (last == 1) {
            types.push_back(false);
            if (i - 2 < 0) return true;
            types.push_back(true);
            last = dp[i - 2][last];
            i -= 2;
        } else {
            types.push_back(last == 2);
            if (i - 1 < 0) return true;
            last = dp[i - 1][last];
            i--;
        }
    }
    return true;
}

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

    ll n, m; cin >> n >> m;
    water.resize(n + 1);
    flowers.resize(m);

    for (ll i = 0; i < n; ++i) {
        cin >> water[i];
        water[i]++;
    }
    water[n] = inf;
    for (ll i = 0; i < m; ++i) {
        cin >> flowers[i];
        flowers[i]++;
        problems.insert(flowers[i]);
    }

    ll l = 0, r = inf; // Last true
    while (r > l) {
        ll mid = l + (r - l) / 2;
        if (ok(mid)) {
            r = mid;
        } else
            l = mid + 1;
    }

    types.clear();
    ok(l);
    if (l == inf) {
        cout << -1;
        return 0;
    }
    if (l == 0) exit(5);
    cout << l << "\n";
    types.pop_back();
    std::reverse(types.begin(), types.end());
    for (auto x : types) {
        cout << (x ? "R" : "L");
    }
    return 0;
}

Compilation message

Main.cpp: In function 'bool ok(ll)':
Main.cpp:43:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (ll i = 0; i < water.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Runtime error 18 ms 3932 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 30 ms 4176 KB Correct
3 Correct 40 ms 1372 KB Correct
4 Correct 634 ms 12828 KB Correct
5 Correct 635 ms 12832 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 497 ms 9504 KB Correct
9 Correct 530 ms 9552 KB Correct
10 Correct 786 ms 11536 KB Correct
11 Correct 207 ms 7532 KB Correct
12 Correct 277 ms 7888 KB Correct
13 Correct 699 ms 10840 KB Correct
14 Correct 731 ms 11256 KB Correct
15 Correct 640 ms 11044 KB Correct
16 Correct 626 ms 10028 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Correct 1 ms 336 KB Correct
4 Correct 1 ms 336 KB Correct
5 Correct 1 ms 336 KB Correct
6 Incorrect 1 ms 336 KB User solution is incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 135 ms 4856 KB Correct
3 Incorrect 951 ms 12136 KB Incorrect string length
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Runtime error 18 ms 3932 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -