oj.uz

Submission #1100627

# Submission time Handle Problem Language Result Execution time Memory
1100627 2024-10-14T10:43:21 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 872 ms 13020 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 && i - 1 >= 0 && 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) {
            if (i - 2 < 0) return true;
            types.push_back(false);
            types.push_back(true);
            last = dp[i - 2][last];
            i -= 2;
        } else {
            if (i - 1 < 0) return true;
            types.push_back(last == 2);
            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;
    }
    cout << l << "\n";
    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 Incorrect 17 ms 3920 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 30 ms 4280 KB Correct
3 Correct 42 ms 1364 KB Correct
4 Correct 674 ms 12948 KB Correct
5 Correct 670 ms 13020 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Incorrect 565 ms 9196 KB Incorrect string length
9 Halted 0 ms 0 KB -

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 137 ms 4708 KB Correct
3 Incorrect 872 ms 12320 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 Incorrect 17 ms 3920 KB Unexpected end of file - token expected
4 Halted 0 ms 0 KB -