답안 #1048073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048073	2024-08-07T21:20:09 Z	PurpleCrayon	Sprinklers (CEOI24_sprinklers)	C++17	26 / 100	162 ms	7256 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const int INF = 2e9+10;
 
#define int ll
void solve() {
    int n, m; cin >> n >> m;
    vector<int> a(n); for (auto& x : a) cin >> x;
    vector<int> b(m); for (auto& x : b) cin >> x;
 
    vector<string> build(n + 1);
    auto can = [&](int x) {
        vector<int> dp(n+1);
        auto upd = [&](int i, int me, string c) {
            if (dp[i] <= me) {
                dp[i] = me;
                build[i] = c;
            }
        };
 
        for (int i = 0; i < n; i++) {
            // dp[i+1] = max(dp[i+1], dp[i]);
            upd(i+1, dp[i], "L");
 
            if (dp[i] >= m) continue;
            int need = b[dp[i]];
            if (a[i] - x <= need && need <= a[i]) {
                int cur = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
                upd(i+1, cur, "L");
                // dp[i+1] = max(dp[i+1], cur);
            }
 
            if (a[i] <= need && need <= a[i] + x) {
                int cur = upper_bound(b.begin(), b.end(), a[i] + x) - b.begin();
                upd(i+1, cur, "R");
                // dp[i+1] = max(dp[i+1], cur);
            }
 
            if (i < n-1 && a[i+1] <= a[i] + x) {
                if (a[i+1] - x <= need && need <= a[i] + x) {
                    int cur = upper_bound(b.begin(), b.end(), a[i] + x) - b.begin();
                    upd(i+2, cur, "RL");
                    // dp[i+2] = max(dp[i+2], cur);
                }
            }
        }
 
        return *max_element(dp.begin(), dp.end()) >= m;
    };
 
    int lo = 0, hi = INF, mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (can(mid)) hi = mid;
        else lo = mid;
        mid = (lo + hi) / 2;
    }
 
    if (!can(hi)) {
        cout << -1 << '\n';
        return;
    }
 
    vector<char> ans(n, '?');
    int c = n;
    while (c > 0) {
        string p = build[c];
        if (sz(p) == 1) {
            ans[c-1] = p[0];
            c--;
        } else if (sz(p) == 2) {
            ans[c-1] = p[1];
            ans[c-2] = p[0];
            c -= 2;
        } else assert(false);
    }
 
    vector<int> ps(m + 1);
    for (int i = 0; i < n; i++) {
        int l = -1, r = -1;
        if (ans[i] == 'L') {
            l = a[i] - hi, r = a[i];
        } else if (ans[i] == 'R') {
            l = a[i], r = a[i] + hi;
        } else assert(false);
 
        int L = lower_bound(b.begin(), b.end(), l) - b.begin();
        int R = upper_bound(b.begin(), b.end(), r) - b.begin() - 1;
        if (L <= R) {
            ps[L]++;
            ps[R+1]--;
        }
    }
 
    for (int i = 1; i <= m; i++)
        ps[i] += ps[i-1];
 
    for (int i = 0; i < m; i++) {
        assert(ps[i]);
    }
 
    cout << hi << '\n';
    for (char c : ans) cout << c;
    cout << '\n';
}

#undef int
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Correct
2	Correct	6 ms	2516 KB	Correct
3	Correct	0 ms	348 KB	Correct
4	Correct	6 ms	1880 KB	Correct
5	Correct	6 ms	1884 KB	Correct
6	Correct	0 ms	348 KB	Correct
7	Correct	0 ms	456 KB	Correct
8	Correct	1 ms	656 KB	Correct
9	Correct	0 ms	348 KB	Correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	7 ms	2652 KB	Correct
3	Correct	8 ms	900 KB	Correct
4	Correct	93 ms	7220 KB	Correct
5	Correct	100 ms	7212 KB	Correct
6	Correct	0 ms	348 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	46 ms	7256 KB	Correct
9	Correct	43 ms	7236 KB	Correct
10	Correct	42 ms	7236 KB	Correct
11	Correct	36 ms	5956 KB	Correct
12	Correct	44 ms	4212 KB	Correct
13	Correct	68 ms	6436 KB	Correct
14	Correct	77 ms	6708 KB	Correct
15	Correct	76 ms	6704 KB	Correct
16	Correct	68 ms	6436 KB	Correct

Subtask #3
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	344 KB	Correct
2	Correct	348 KB	Correct
3	Correct	344 KB	Correct
4	Correct	348 KB	Correct
5	Correct	464 KB	Correct
6	Correct	348 KB	Correct
7	Correct	348 KB	Correct
8	Correct	348 KB	Correct
9	Correct	348 KB	Correct
10	Correct	348 KB	Correct
11	Correct	348 KB	Correct
12	Correct	348 KB	Correct
13	Correct	348 KB	Correct
14	Correct	348 KB	Correct
15	Correct	348 KB	Correct
16	Correct	348 KB	Correct
17	Correct	348 KB	Correct
18	Correct	348 KB	Correct
19	Correct	348 KB	Correct
20	Correct	348 KB	Correct

Subtask #4
0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	28 ms	3152 KB	Correct
3	Correct	162 ms	7248 KB	Correct
4	Correct	145 ms	7212 KB	Correct
5	Correct	144 ms	7232 KB	Correct
6	Correct	140 ms	7212 KB	Correct
7	Correct	143 ms	7232 KB	Correct
8	Correct	142 ms	7212 KB	Correct
9	Correct	144 ms	7232 KB	Correct
10	Correct	140 ms	7192 KB	Correct
11	Correct	148 ms	7236 KB	Correct
12	Correct	0 ms	348 KB	Correct
13	Correct	0 ms	348 KB	Correct
14	Incorrect	38 ms	5940 KB	User solution is worse than jury's solution
15	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	0 ms	348 KB	Correct
3	Correct	6 ms	2516 KB	Correct
4	Correct	0 ms	348 KB	Correct
5	Correct	6 ms	1880 KB	Correct
6	Correct	6 ms	1884 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	0 ms	456 KB	Correct
9	Correct	1 ms	656 KB	Correct
10	Correct	0 ms	348 KB	Correct
11	Correct	7 ms	2652 KB	Correct
12	Correct	8 ms	900 KB	Correct
13	Correct	93 ms	7220 KB	Correct
14	Correct	100 ms	7212 KB	Correct
15	Correct	0 ms	348 KB	Correct
16	Correct	0 ms	348 KB	Correct
17	Correct	46 ms	7256 KB	Correct
18	Correct	43 ms	7236 KB	Correct
19	Correct	42 ms	7236 KB	Correct
20	Correct	36 ms	5956 KB	Correct
21	Correct	44 ms	4212 KB	Correct
22	Correct	68 ms	6436 KB	Correct
23	Correct	77 ms	6708 KB	Correct
24	Correct	76 ms	6704 KB	Correct
25	Correct	68 ms	6436 KB	Correct
26	Correct	0 ms	344 KB	Correct
27	Correct	0 ms	348 KB	Correct
28	Correct	0 ms	464 KB	Correct
29	Correct	0 ms	348 KB	Correct
30	Correct	0 ms	348 KB	Correct
31	Correct	0 ms	348 KB	Correct
32	Correct	0 ms	348 KB	Correct
33	Correct	0 ms	348 KB	Correct
34	Correct	0 ms	348 KB	Correct
35	Correct	0 ms	348 KB	Correct
36	Correct	0 ms	348 KB	Correct
37	Correct	0 ms	348 KB	Correct
38	Correct	0 ms	348 KB	Correct
39	Correct	0 ms	348 KB	Correct
40	Correct	0 ms	348 KB	Correct
41	Correct	0 ms	348 KB	Correct
42	Correct	0 ms	348 KB	Correct
43	Correct	0 ms	348 KB	Correct
44	Correct	28 ms	3152 KB	Correct
45	Correct	162 ms	7248 KB	Correct
46	Correct	145 ms	7212 KB	Correct
47	Correct	144 ms	7232 KB	Correct
48	Correct	140 ms	7212 KB	Correct
49	Correct	143 ms	7232 KB	Correct
50	Correct	142 ms	7212 KB	Correct
51	Correct	144 ms	7232 KB	Correct
52	Correct	140 ms	7192 KB	Correct
53	Correct	148 ms	7236 KB	Correct
54	Correct	0 ms	348 KB	Correct
55	Correct	0 ms	348 KB	Correct
56	Incorrect	38 ms	5940 KB	User solution is worse than jury's solution
57	Halted	0 ms	0 KB	-

답안 #1048073

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 3.0 / 3.0

Subtask #2 6.0 / 6.0

Subtask #3 17.0 / 17.0

Subtask #4 0.0 / 27.0

Subtask #5 0.0 / 47.0

Subtask #0
0.0 / 0.0

Subtask #1
3.0 / 3.0

Subtask #2
6.0 / 6.0

Subtask #3
17.0 / 17.0

Subtask #4
0.0 / 27.0

Subtask #5
0.0 / 47.0