Submission #1039563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039563	2024-07-31T04:36:20 Z	정민찬(#10992)	Sprinklers (CEOI24_sprinklers)	C++17	6 / 100	468 ms	4384 KB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, M;
int s[100010], f[100010];

pair<int,int> ran(int l, int r) {
    int retl = lower_bound(f+1, f+M+1, l) - f;
    int retr = upper_bound(f+1, f+M+1, r) - f - 1;
    return {retl, retr};
}

int dp[100010], prv[100010];

bool solve(int X) {
    dp[0] = 0;
    for (int i=1; i<=N; i++) {
        dp[i] = dp[i-1]; prv[i] = 0;
        int retl, retr;
        tie(retl, retr) = ran(s[i], s[i]-X);
        if (dp[i-1] >= retl-1) {
            if (dp[i] < retr) {
                dp[i] = retr;
                prv[i] = 1;
            }
        }
        tie(retl, retr) = ran(s[i], s[i]+X);
        if (dp[i-1] >= retl-1) {
            if (dp[i] < retr) {
                dp[i] = retr;
                prv[i] = 2;
            }
        }
        if (i != 1) {
            tie(retl, retr) = ran(s[i] - X, s[i-1] + X);
            if (dp[i-2] >= retl-1) {
                if (dp[i] < retr) {
                    dp[i] = retr;
                    prv[i] = 3;
                }
            }
        }
    }
    return dp[N] == M;
}

int ans[100010];

int main() {
    scanf("%d %d", &N, &M);
    for (int i=1; i<=N; i++) {
        scanf("%d", &s[i]);
    }
    for (int i=1; i<=M; i++) {
        scanf("%d", &f[i]);
    }
    int lo = 0, hi = 1e9 + 10;
    while (lo < hi) {
        int mid = lo + hi >> 1;
        if (solve(mid)) hi = mid;
        else lo = mid + 1;
    }
    if (lo == 1e9 + 10) {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", lo);
    solve(lo);
    int x = N;
    while (x) {
        if (prv[x] <= 1) {
            ans[x] = 0;
            x --;
        }
        else if (prv[x] == 2) {
            ans[x] = 1;
            x --;
        }
        else {
            ans[x] = 0;
            ans[x-1] = 1;
            x -= 2;
        }
    }
    for (int i=1; i<=N; i++) {
        if (ans[i] == 0) printf("L");
        else printf("R");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:61:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
Main.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d", &s[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &f[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Correct
2	Correct	0 ms	348 KB	Correct

Subtask #1
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Correct
2	Incorrect	10 ms	744 KB	User solution is worse than jury's solution
3	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Correct
2	Correct	25 ms	600 KB	Correct
3	Correct	37 ms	592 KB	Correct
4	Correct	468 ms	4384 KB	Correct
5	Correct	456 ms	4180 KB	Correct
6	Correct	0 ms	348 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	306 ms	4188 KB	Correct
9	Correct	362 ms	4188 KB	Correct
10	Correct	373 ms	4188 KB	Correct
11	Correct	145 ms	2900 KB	Correct
12	Correct	243 ms	2472 KB	Correct
13	Correct	402 ms	3384 KB	Correct
14	Correct	397 ms	3508 KB	Correct
15	Correct	468 ms	3608 KB	Correct
16	Correct	436 ms	3152 KB	Correct