oj.uz

Submission #1075412

# Submission time Handle Problem Language Result Execution time Memory
1075412 2024-08-26T05:42:26 Z GrindMachine Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 101 ms 10180 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i) 
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
	x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
	x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
	return "'"+s+"'";
}

string to_string(const char *s){
	return to_string((string)s);
}

string to_string(bool b){
	return b?"true":"false";
}

template<typename A>
string to_string(A v){
	string res = "{";
	trav(x,v){
		res += to_string(x)+",";
	}
	if(res.back() == ',') res.pop_back();
	res += "}";
	return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
	return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << #x << " = "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

void solve(int test_case){
	ll n,m; cin >> n >> m;
	vector<ll> a(n+5), b(m+5);
	rep1(i,n) cin >> a[i];
	rep1(i,m) cin >> b[i];	
	rep1(i,m){
		if(binary_search(a.begin()+1,a.begin()+n+1,b[i])){
			b[i] = -1;
		}
	}

	vector<array<ll,3>> c;
	rep1(i,n) c.pb({a[i],i,1});
	rep1(i,m){
		if(b[i] != -1){
			c.pb({b[i],i,2});
		}
	}
	sort(all(c));

	vector<char> ans(n+5);

	auto ok = [&](ll mid){
		ll mnf = inf2, mxs = -inf2;

		for(auto [x,i,t] : c){
			if(t == 1){
				// sprinkler
				if(mnf != inf2){
					if(x-mnf > mid){
						return false;
					}
					ans[i] = 'L';
					mnf = inf2;
				}
				else{
					mxs = x+mid;
					ans[i] = 'R';
				}
			}
			else{
				// flower
				if(mxs >= x) conts;
				amin(mnf,x);
			}
		}

		return mnf == inf2;
	};

	ll lo = 0, hi = inf1;
	ll best = -1;

	while(lo <= hi){
		ll mid = (lo+hi) >> 1;
		if(ok(mid)){
			best = mid;
			hi = mid-1;
		}
		else{
			lo = mid+1;
		}
	}	

	cout << best << endl;
	if(best == -1) return;

	ok(best);
	rep1(i,n) cout << ans[i];
	cout << endl;
}

int main(){
	int t = 1;
	// cin >> t;

	rep1(i,t){
		solve(i);
	}

	return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 33 ms 4276 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 33 ms 5384 KB Correct
5 Correct 33 ms 5328 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 7 ms 1624 KB Correct
9 Correct 1 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 39 ms 4304 KB Correct
3 Correct 6 ms 1112 KB Correct
4 Correct 94 ms 10136 KB Correct
5 Correct 101 ms 10180 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 67 ms 6972 KB Correct
9 Correct 69 ms 7108 KB Correct
10 Correct 85 ms 10180 KB Correct
11 Correct 38 ms 5232 KB Correct
12 Correct 50 ms 5828 KB Correct
13 Correct 60 ms 8896 KB Correct
14 Correct 65 ms 9224 KB Correct
15 Correct 68 ms 9408 KB Correct
16 Correct 52 ms 5932 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 1 ms 348 KB Correct
5 Incorrect 1 ms 348 KB User solution is worse than jury's solution
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 46 ms 4496 KB Correct
3 Incorrect 99 ms 10180 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 33 ms 4276 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 33 ms 5384 KB Correct
6 Correct 33 ms 5328 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 7 ms 1624 KB Correct
10 Correct 1 ms 348 KB Correct
11 Correct 39 ms 4304 KB Correct
12 Correct 6 ms 1112 KB Correct
13 Correct 94 ms 10136 KB Correct
14 Correct 101 ms 10180 KB Correct
15 Correct 0 ms 344 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 67 ms 6972 KB Correct
18 Correct 69 ms 7108 KB Correct
19 Correct 85 ms 10180 KB Correct
20 Correct 38 ms 5232 KB Correct
21 Correct 50 ms 5828 KB Correct
22 Correct 60 ms 8896 KB Correct
23 Correct 65 ms 9224 KB Correct
24 Correct 68 ms 9408 KB Correct
25 Correct 52 ms 5932 KB Correct
26 Correct 1 ms 348 KB Correct
27 Correct 1 ms 348 KB Correct
28 Incorrect 1 ms 348 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -