oj.uz

답안 #1100596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100596 2024-10-14T09:46:16 Z crafticat Sprinklers (CEOI24_sprinklers) C++17
6 / 100
 845 ms 12932 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 + 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;
    }
    if (l == 0) 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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct

Subtask #1
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Correct
2 Runtime error 21 ms 3920 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 32 ms 4164 KB Correct
3 Correct 39 ms 1372 KB Correct
4 Correct 637 ms 12932 KB Correct
5 Correct 619 ms 12832 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Correct 478 ms 9068 KB Correct
9 Correct 504 ms 9564 KB Correct
10 Correct 829 ms 11576 KB Correct
11 Correct 200 ms 7456 KB Correct
12 Correct 266 ms 7888 KB Correct
13 Correct 653 ms 10736 KB Correct
14 Correct 645 ms 11080 KB Correct
15 Correct 635 ms 11100 KB Correct
16 Correct 637 ms 10016 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 134 ms 4820 KB Correct
3 Incorrect 845 ms 12320 KB Incorrect string length
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Runtime error 21 ms 3920 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -