oj.uz

Submission #1100603

# Submission time Handle Problem Language Result Execution time Memory
1100603 2024-10-14T10:18:00 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 884 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;
    }
    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 Incorrect 19 ms 3920 KB Unexpected end of file - token expected
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 38 ms 4224 KB Correct
3 Correct 44 ms 1352 KB Correct
4 Correct 680 ms 12832 KB Correct
5 Correct 742 ms 12832 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 512 ms 9324 KB Correct
9 Correct 520 ms 9516 KB Correct
10 Correct 799 ms 11552 KB Correct
11 Correct 221 ms 7524 KB Correct
12 Correct 289 ms 7888 KB Correct
13 Correct 704 ms 10780 KB Correct
14 Correct 729 ms 11040 KB Correct
15 Correct 672 ms 11092 KB Correct
16 Correct 623 ms 9852 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 138 ms 4812 KB Correct
3 Incorrect 884 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 19 ms 3920 KB Unexpected end of file - token expected
4 Halted 0 ms 0 KB -