oj.uz

답안 #1087800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087800 2024-09-13T08:53:32 Z mychecksedad Sprinklers (CEOI24_sprinklers) C++17
26 / 100
 174 ms 3220 KB 
#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

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

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

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

Subtask #4
0.0 / 27.0

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

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