Submission #1087800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1087800	2024-09-13T08:53:32 Z	mychecksedad	Sprinklers (CEOI24_sprinklers)	C++17	26 / 100	174 ms	3220 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1e5+100;


int n, m, a[N], b[N];
int get(int l, int r){
	if(r < l) return 0;
	return upper_bound(b+1, b+1+m, r) - lower_bound(b+1, b+1+m, l);
}
void solve(){
	cin >> n >> m;
	vector<pii> v;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		v.pb({a[i], 1});
	}
	for(int i = 1; i <= m; ++i){
		cin >> b[i];
		v.pb({b[i], 0});
	}
	sort(all(v));
	string soll;
	int l = 0, r = 1e9+2, ans = -1;
	while(l <= r){
		int k = l+r>>1;
		string sol = "";
		bool ok = 1;
		int last_covered = -2e9;
		for(int i = 1; i <= n; ++i){
			if(last_covered >= a[i] - 1){
				sol += 'R';
				last_covered = a[i] + k;
				continue;
			}
			int left_uncovered = get(last_covered + 1, a[i] - 1);
			if(left_uncovered > get(a[i] - k, a[i] - 1)){
				ok = 0;
				break;
			}
			if(left_uncovered == 0){
				sol += 'R';
				last_covered = a[i] + k;
			}else{
				if(i + 1 <= n){
					int right_cover = get(a[i] + 1, min(a[i + 1] - 1, a[i] + k));
					if(right_cover == 0){
						sol += 'L';
						last_covered = a[i];
					}else if(right_cover > 0){
						if(a[i + 1] - k < a[i] && left_uncovered <= get(a[i + 1] - k, a[i] - 1)){
							sol += 'R';
							sol += 'L';
							last_covered = a[i] + k;
							++i;
							continue;
						}else{
							sol += 'L';
							last_covered = a[i];
							continue;
						}
					}
				}else{
					sol += 'L';
					last_covered = a[i];
				}
			}
		}
		if(b[m] > last_covered) ok = 0;


		if(ok){
			ans = k;
			soll = sol;
			r = k - 1;
		}else{
			l = k + 1;
		}
	}

	cout << ans << '\n';
	if(ans != -1){
		cout << soll;
	}
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int k = l+r>>1;
      |           ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Correct
2	Correct	8 ms	1820 KB	Correct
3	Correct	0 ms	348 KB	Correct
4	Correct	8 ms	1780 KB	Correct
5	Correct	9 ms	1752 KB	Correct
6	Correct	0 ms	348 KB	Correct
7	Correct	1 ms	348 KB	Correct
8	Correct	2 ms	860 KB	Correct
9	Correct	1 ms	348 KB	Correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	14 ms	1752 KB	Correct
3	Correct	4 ms	600 KB	Correct
4	Correct	35 ms	3220 KB	Correct
5	Correct	43 ms	3204 KB	Correct
6	Correct	0 ms	348 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	24 ms	3212 KB	Correct
9	Correct	26 ms	3032 KB	Correct
10	Correct	36 ms	3028 KB	Correct
11	Correct	20 ms	2008 KB	Correct
12	Correct	16 ms	2004 KB	Correct
13	Correct	31 ms	3032 KB	Correct
14	Correct	35 ms	3028 KB	Correct
15	Correct	49 ms	3032 KB	Correct
16	Correct	32 ms	3028 KB	Correct

Subtask #3
17.0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Correct
2	Correct	348 KB	Correct
3	Correct	348 KB	Correct
4	Correct	348 KB	Correct
5	Correct	344 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	344 KB	Correct
18	Correct	348 KB	Correct
19	Correct	348 KB	Correct
20	Correct	348 KB	Correct

Subtask #4
0.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	45 ms	1756 KB	Correct
3	Correct	165 ms	3120 KB	Correct
4	Correct	174 ms	3124 KB	Correct
5	Correct	172 ms	3140 KB	Correct
6	Correct	167 ms	3032 KB	Correct
7	Correct	170 ms	3120 KB	Correct
8	Correct	165 ms	3032 KB	Correct
9	Correct	161 ms	3028 KB	Correct
10	Correct	158 ms	3140 KB	Correct
11	Correct	170 ms	3196 KB	Correct
12	Correct	0 ms	348 KB	Correct
13	Correct	0 ms	348 KB	Correct
14	Correct	53 ms	2028 KB	Correct
15	Correct	57 ms	2000 KB	Correct
16	Correct	54 ms	1992 KB	Correct
17	Correct	25 ms	3152 KB	Correct
18	Correct	24 ms	3216 KB	Correct
19	Correct	35 ms	3032 KB	Correct
20	Correct	90 ms	3100 KB	Correct
21	Correct	93 ms	3028 KB	Correct
22	Correct	53 ms	3032 KB	Correct
23	Incorrect	45 ms	3120 KB	User solution is worse than jury's solution
24	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Correct
2	Correct	0 ms	348 KB	Correct
3	Correct	8 ms	1820 KB	Correct
4	Correct	0 ms	348 KB	Correct
5	Correct	8 ms	1780 KB	Correct
6	Correct	9 ms	1752 KB	Correct
7	Correct	0 ms	348 KB	Correct
8	Correct	1 ms	348 KB	Correct
9	Correct	2 ms	860 KB	Correct
10	Correct	1 ms	348 KB	Correct
11	Correct	14 ms	1752 KB	Correct
12	Correct	4 ms	600 KB	Correct
13	Correct	35 ms	3220 KB	Correct
14	Correct	43 ms	3204 KB	Correct
15	Correct	0 ms	348 KB	Correct
16	Correct	0 ms	348 KB	Correct
17	Correct	24 ms	3212 KB	Correct
18	Correct	26 ms	3032 KB	Correct
19	Correct	36 ms	3028 KB	Correct
20	Correct	20 ms	2008 KB	Correct
21	Correct	16 ms	2004 KB	Correct
22	Correct	31 ms	3032 KB	Correct
23	Correct	35 ms	3028 KB	Correct
24	Correct	49 ms	3032 KB	Correct
25	Correct	32 ms	3028 KB	Correct
26	Correct	0 ms	348 KB	Correct
27	Correct	0 ms	348 KB	Correct
28	Correct	0 ms	344 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	344 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	45 ms	1756 KB	Correct
45	Correct	165 ms	3120 KB	Correct
46	Correct	174 ms	3124 KB	Correct
47	Correct	172 ms	3140 KB	Correct
48	Correct	167 ms	3032 KB	Correct
49	Correct	170 ms	3120 KB	Correct
50	Correct	165 ms	3032 KB	Correct
51	Correct	161 ms	3028 KB	Correct
52	Correct	158 ms	3140 KB	Correct
53	Correct	170 ms	3196 KB	Correct
54	Correct	0 ms	348 KB	Correct
55	Correct	0 ms	348 KB	Correct
56	Correct	53 ms	2028 KB	Correct
57	Correct	57 ms	2000 KB	Correct
58	Correct	54 ms	1992 KB	Correct
59	Correct	25 ms	3152 KB	Correct
60	Correct	24 ms	3216 KB	Correct
61	Correct	35 ms	3032 KB	Correct
62	Correct	90 ms	3100 KB	Correct
63	Correct	93 ms	3028 KB	Correct
64	Correct	53 ms	3032 KB	Correct
65	Incorrect	45 ms	3120 KB	User solution is worse than jury's solution
66	Halted	0 ms	0 KB	-

Submission #1087800

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