Submission #1192336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192336		SmuggingSpun	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	42 ms	1280 KiB

Main

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int INF = 1e9 + 1;
const int lim = 1e5 + 5;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
int n, m, s[lim], f[lim];
namespace sub1{
	void solve(){
		if(f[1] < s[1] && s[1] < f[m]){
			return void(cout << -1);
		}
		if(s[1] <= f[1]){
			cout << f[m] - s[1] << "\nR";
		}
		else{
			cout << s[1] - f[1] << "\nL";
		}
	}
}
namespace sub2{
	void solve(){
		int low = 1, high = INF, ans;
		while(low <= high){
			int mid = (low + high) >> 1;
			vector<int>cnt(m + 2, 0);
			for(int i = 1; i < n; i += 3){
				cnt[lower_bound(f + 1, f + m + 1, s[i + 1] - mid) - f]++;
				cnt[upper_bound(f + 1, f + m + 2, s[i + 1] + mid) - f]--;
			}
			bool flag = true;
			for(int i = 1; i <= m; i++){
				if((cnt[i] += cnt[i - 1]) == 0){
					flag = false;
					break;
				}
			}
			if(flag){
				high = (ans = mid) - 1;
			}
			else{
				low = mid + 1;
			}
		}
		cout << ans << "\n";
		for(int i = 1; i < n; i += 3){
			cout << "LRL";
		}
	}
}
namespace sub3{
	void solve(){
		int ans_k = INF, ans_mask = -1;
		for(int mask = (1 << n) - 1; mask > -1; mask--){
			int low = 1, high = ans_k - 1;
			while(low <= high){
				int mid = (low + high) >> 1;
				vector<int>cnt(m + 2, 0);
				for(int i = 0; i < n; i++){
					if(1 << i & mask){
						cnt[lower_bound(f + 1, f + m + 1, s[i + 1] - mid) - f]++;
						cnt[upper_bound(f + 1, f + m + 2, s[i + 1]) - f]--;
					}
					else{
						cnt[lower_bound(f + 1, f + m + 1, s[i + 1]) - f]++;
						cnt[upper_bound(f + 1, f + m + 2, s[i + 1] + mid) - f]--;
					}
				}
				bool flag = true;
				for(int i = 1; i <= m; i++){
					if((cnt[i] += cnt[i - 1]) == 0){
						flag = false;
						break;
					}
				}
				if(flag){
					high = (ans_k = mid) - 1;
					ans_mask = mask;
				}
				else{
					low = mid + 1;
				}
			}
		}
		if(ans_mask == -1){
			return void(cout << -1);
		}
		cout << ans_k << "\n";
		for(int i = 0; i < n; i++){
			cout << ((1 << i & ans_mask) ? 'L' : 'R');
		}
	}
}
namespace sub45{
	void solve(){
		int low = 1, high = INF, ans = -1;
		while(low <= high){
			int mid = (low + high) >> 1, i = 1, j = 1, r = s[1];
			bool flag = true;
			for(; i <= n; i++){
				if(f[j] >= s[i]){
					while(f[j] <= s[i] + mid){
						j++;
					}
				}
				else if(f[j] < s[i] - mid){
					flag = false;
					break;
				}
				else if(s[i + 1] - mid <= f[j] && *upper_bound(f + 1, f + m + 2, s[i]) < s[i + 1]){
					r = s[i] + mid;
				}
				else{
					while(f[j] <= max(r, s[i])){
						j++;
					}
				}
			}
			if(!flag || j <= m){
				low = mid + 1;
			}
			else{
				high = (ans = mid) - 1;
			}
		}
		cout << ans << "\n";
		if(ans != -1){
			for(int i = 1, j = 1, r = s[1]; i <= n; i++){
				if(f[j] >= s[i]){
					while(f[j] <= s[i] + ans){
						j++;
					}
					cout << "R";
				}
				else if(s[i + 1] - ans <= f[j] && *upper_bound(f + 1, f + m + 2, s[i]) < s[i + 1]){
					r = s[i] + ans;
					cout << "R";
				}
				else{
					while(f[j] <= max(r, s[i])){
						j++;
					}
					cout << "L";
				}
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	bool is_sub2 = bool(n % 3 == 0);
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		if(i % 3 == 0 && s[i] != s[i - 2]){
			is_sub2 = false;
		}
	}
	for(int i = 1; i <= m; i++){
		cin >> f[i];
	}
	f[m + 1] = INF << 1;
	s[n + 1] = 0;
	sub45::solve();
	return 0;
	if(n == 1){
		sub1::solve();
	}
	else if(is_sub2){
		sub2::solve();
	}
	else if(n <= 10 && m <= 1000){
		sub3::solve();
	}
	else{
		sub45::solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:156:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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