oj.uz

Submission #1047545

# Submission time Handle Problem Language Result Execution time Memory
1047545 2024-08-07T13:57:29 Z Tsovak Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 103 ms 9556 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout << fixed << setprecision(x);
	return;
}

ll gcd0(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm0(ll a, ll b)
{
	return a / gcd0(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) return false;
	for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrtl(ld(a)));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrtl(ld(a)));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans *= ll(i);
	return ans;
}

ll factorial_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
	return ans;
}

// -------------------- Solution -------------------- //

const int N = 100005, M = 200005;
pr<int, int> a[N];
int b[M];
bool ans[N];
int n, m;

set<int> st;

int dp[N];
int from[N];

bool covers(int l, int r, int e) { return l <= b[e] && b[e] <= r; }

bool check(int h)
{
	int i, j;

	for (i = 0; i <= n; i++) dp[i] = from[i] = 0;

	dp[0] = 1;


	for (i = 0; i < n; i++) {
		dp[i + 1] = dp[i];

		if (covers(a[i + 1].ff - h, a[i + 1].ff, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff) - b;

			if (dp[i + 1] < j) {
				dp[i + 1] = j;
				from[i + 1] = 1;
			}
		}

		if (covers(a[i + 1].ff, a[i + 1].ff + h, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff + h) - b;

			if (dp[i + 1] < j) {
				dp[i + 1] = j;
				from[i + 1] = 2;
			}
		}


		if (i + 2 <= n && a[i + 2].ff - a[i].ff < h && covers(a[i + 2].ff - h, a[i + 1].ff + h, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff + h) - b;

			if (dp[i + 2] < j) {
				dp[i + 2] = j;
				from[i + 2] = 3;
			}
		}
	}

	return dp[n] == m + 1;
}

void solve()
{
	int i, j;

	cin >> n >> m;

	for (i = 1; i <= n; i++) {
		cin >> a[i].ff;
		a[i].ss = i;
	}
	for (i = 1; i <= m; i++) {
		cin >> b[i];
		st.insert(b[i]);
	}

	sort(a + 1, a + n + 1);

	m = sz(st); i = 0;
	for (auto p : st) b[++i] = p;

	if (n == 1) {
		if (a[1].ff <= b[1]) cout << b[m] - a[1].ff << "\nR\n";
		else if (b[m] <= a[1].ff) cout << a[1].ff - b[1] << "\nL\n";
		else cout << "-1\n";

		return;
	}


	int l = 0, r = MAX, mid;

	while (l < r) {
		mid = (l + r) / 2;

		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	check(l);

	i = n;
	while (i) {
		if (from[i] <= 1) i--;
		else if (from[i] == 2) {
			ans[i] = 1;
			i--;
		}
		else {
			ans[i - 1] = 1;
			i -= 2;
		}
	}


	cout << l << "\n";
	for (i = 1; i <= n; i++) cout << (ans[i] ? 'R' : 'L');
	cout << "\n";

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:243:9: warning: unused variable 'j' [-Wunused-variable]
  243 |  int i, j;
      |         ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 0 ms 2524 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2524 KB Correct
2 Correct 14 ms 6236 KB Correct
3 Correct 1 ms 2392 KB Correct
4 Correct 19 ms 8020 KB Correct
5 Correct 19 ms 7964 KB Correct
6 Correct 0 ms 2396 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 3 ms 3420 KB Correct
9 Correct 1 ms 2396 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 26 ms 6480 KB Correct
3 Correct 6 ms 2908 KB Correct
4 Correct 79 ms 9512 KB Correct
5 Correct 81 ms 9556 KB Correct
6 Correct 1 ms 2392 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 65 ms 6032 KB Correct
9 Correct 65 ms 6484 KB Correct
10 Correct 47 ms 8784 KB Correct
11 Correct 15 ms 3932 KB Correct
12 Correct 44 ms 8028 KB Correct
13 Correct 75 ms 6488 KB Correct
14 Correct 73 ms 7228 KB Correct
15 Correct 68 ms 7524 KB Correct
16 Correct 74 ms 5720 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 0 ms 2524 KB Correct
3 Correct 1 ms 2396 KB Correct
4 Correct 1 ms 2396 KB Correct
5 Incorrect 0 ms 2396 KB K is out of range
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 45 ms 6532 KB Correct
3 Incorrect 103 ms 9320 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 0 ms 2396 KB Correct
2 Correct 0 ms 2524 KB Correct
3 Correct 14 ms 6236 KB Correct
4 Correct 1 ms 2392 KB Correct
5 Correct 19 ms 8020 KB Correct
6 Correct 19 ms 7964 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 0 ms 2396 KB Correct
9 Correct 3 ms 3420 KB Correct
10 Correct 1 ms 2396 KB Correct
11 Correct 26 ms 6480 KB Correct
12 Correct 6 ms 2908 KB Correct
13 Correct 79 ms 9512 KB Correct
14 Correct 81 ms 9556 KB Correct
15 Correct 1 ms 2392 KB Correct
16 Correct 0 ms 2396 KB Correct
17 Correct 65 ms 6032 KB Correct
18 Correct 65 ms 6484 KB Correct
19 Correct 47 ms 8784 KB Correct
20 Correct 15 ms 3932 KB Correct
21 Correct 44 ms 8028 KB Correct
22 Correct 75 ms 6488 KB Correct
23 Correct 73 ms 7228 KB Correct
24 Correct 68 ms 7524 KB Correct
25 Correct 74 ms 5720 KB Correct
26 Correct 1 ms 2396 KB Correct
27 Correct 1 ms 2396 KB Correct
28 Incorrect 0 ms 2396 KB K is out of range
29 Halted 0 ms 0 KB -