oj.uz

Submission #1100584

# Submission time Handle Problem Language Result Execution time Memory
1100584 2024-10-14T09:26:05 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 897 ms 12148 KB 
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using pi = pair<int,int>;


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

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

int pos(V<V<int>> &dp, int i, int lastR, int r) {
    int leftR = -1;
    if (i >= 0) {
        for (int 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(int r) {
    V<V<int>> dp(water.size() + 1, vi(3,-1));

    for (int i = 0; i < water.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int 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
    int last = dp[water.size() - 1][2];
    int i = water.size() - 1;
    if (last == -1) return false;
    while (last != -1) {
        if (last == 1) {
            types.push_back(false);
            types.push_back(true);
            if (i - 2 < 0) return 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);

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

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

    int l = 0, r = inf; // Last true
    while (r > l) {
        int 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(int)':
Main.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int 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 564 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 KB Correct
2 Incorrect 24 ms 3660 KB User solution is incorrect
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 34 ms 3940 KB Correct
3 Correct 41 ms 1124 KB Correct
4 Correct 655 ms 12044 KB Correct
5 Correct 706 ms 12148 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 475 ms 8496 KB Correct
9 Correct 608 ms 8816 KB Correct
10 Correct 759 ms 10748 KB Correct
11 Correct 215 ms 7200 KB Correct
12 Correct 259 ms 7436 KB Correct
13 Correct 721 ms 10016 KB Correct
14 Correct 698 ms 10524 KB Correct
15 Correct 622 ms 10696 KB Correct
16 Correct 613 ms 9248 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 564 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 4196 KB Correct
3 Incorrect 897 ms 11340 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 564 KB Correct
3 Incorrect 24 ms 3660 KB User solution is incorrect
4 Halted 0 ms 0 KB -