oj.uz

Submission #1100590

# Submission time Handle Problem Language Result Execution time Memory
1100590 2024-10-14T09:34:51 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 842 ms 12160 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;
    }
    if (l == 0 && m == 1) 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(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 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 3664 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 32 ms 3736 KB Correct
3 Correct 39 ms 1300 KB Correct
4 Correct 621 ms 12064 KB Correct
5 Correct 616 ms 12160 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 476 ms 8488 KB Correct
9 Correct 519 ms 8792 KB Correct
10 Correct 790 ms 10868 KB Correct
11 Correct 207 ms 7196 KB Correct
12 Correct 269 ms 7376 KB Correct
13 Correct 672 ms 10004 KB Correct
14 Correct 674 ms 10576 KB Correct
15 Correct 610 ms 10528 KB Correct
16 Correct 602 ms 9256 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 504 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 132 ms 4384 KB Correct
3 Incorrect 842 ms 11536 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 3664 KB User solution is incorrect
4 Halted 0 ms 0 KB -