Submission #1123110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123110		peacebringer1667	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	45 ms	1352 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 1e9 + 4e7;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}
template <class t1> inline void print_vector(const vector <t1> &vec){
	for (t1 x : vec) cout << x << " ";cout << "\n";
}

int S[maxn],F[maxn];
bool state[maxn],a[maxn];

void input(int n,int m){
	for (int i = 1 ; i <= n ; i++) cin >> S[i];
	for (int i = 1 ; i <= m ; i++) cin >> F[i];
}

bool possible(int len,int n,int m){
	int p = 1;
	for (int i = 1 ; i <= n ; i++){
		if (p > m) break;
		
		int l,r,x = S[i];
		
		//get range of l..r
		if (F[p] < x){
			l = x - len,r = x,state[i] = 0;
		}
		else{
			l = x,r = x + len,state[i] = 1;
		}
		
		while (p <= m && F[p] >= l && F[p] <= r) p++;
	}
	return (p > m);
}

void state_to_answer(int n){
	for (int i = 1 ; i <= n ; i++) a[i] = state[i];
}
bool solve(int n,int m){
	int l = 0,r = inf,dist = inf;
	while (l <= r){
		int w = (l + r)/2;
		if (possible(w,n,m)){
			dist = w;
			state_to_answer(n);
			r = w - 1;
		}
		else l = w + 1;
	}
	
	if (dist >= inf) return 0;
	//don't forget to return 1 after writing and tracing
	
	cout << dist << "\n";
	for (int i = 1 ; i <= n ; i++){
		if (!a[i]) cout << "L";
		if (a[i]) cout << "R";
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
//    freopen("SPRINKLER.inp","r",stdin);
//    freopen("SPRINKLER.out","w",stdout);
    
    int n,m;
    cin >> n >> m;
    input(n,m);
    
    if (!solve(n,m)) cout << -1;
    
	return 0;
}

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