Submission #1087760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087760		mychecksedad	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	56 ms	5156 KiB

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];
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, ans = -1;
	while(l <= r){
		int k = l+r>>1;
		string sol = "";
		bool ok = 1;
		int last = -1e9, last_not_covered = 2e9;
		for(int i = 0; i < n+m; ++i){
			if(v[i].ss == 0){
				if(last >= v[i].ff){
					continue;
				}
				last_not_covered = min(last_not_covered, v[i].ff);
			}else{
				if(last_not_covered != 2e9 && last_not_covered < v[i].ff){
					if(v[i].ff - last_not_covered > k){
						ok = 0;
						break;
					}
					last_not_covered = 2e9;
					sol += 'L';
				}else{
					last_not_covered = 2e9;
					last = v[i].ff + k;
					sol += 'R';
				}
			}
		}
		if(last_not_covered != 2e9) 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 (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47