oj.uz

Submission #1100593

# Submission time Handle Problem Language Result Execution time Memory
1100593 2024-10-14T09:36:15 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 878 ms 12176 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;
    }
    problems.erase(water[0]);
    if (l == 0 && problems.empty()) 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 20 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 37 ms 3920 KB Correct
3 Correct 39 ms 1292 KB Correct
4 Correct 657 ms 12176 KB Correct
5 Correct 671 ms 12064 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 490 ms 8484 KB Correct
9 Correct 505 ms 8848 KB Correct
10 Correct 813 ms 10836 KB Correct
11 Correct 202 ms 7208 KB Correct
12 Correct 260 ms 7376 KB Correct
13 Correct 727 ms 10040 KB Correct
14 Correct 696 ms 10428 KB Correct
15 Correct 633 ms 10472 KB Correct
16 Correct 624 ms 9312 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 139 ms 4392 KB Correct
3 Incorrect 878 ms 11528 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 20 ms 3664 KB User solution is incorrect
4 Halted 0 ms 0 KB -