oj.uz

Submission #1047546

# Submission time Handle Problem Language Result Execution time Memory
1047546 2024-08-07T13:59:11 Z Tsovak Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 105 ms 7596 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 = 1e9, mid;

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

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

	check(l);

	assert(l <= 1e9);

	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 1 ms 2392 KB Correct
2 Correct 0 ms 2392 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Correct
2 Correct 17 ms 5468 KB Correct
3 Correct 0 ms 2396 KB Correct
4 Correct 19 ms 7000 KB Correct
5 Correct 20 ms 7220 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 0 ms 2396 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Correct
2 Correct 21 ms 5468 KB Correct
3 Correct 6 ms 2764 KB Correct
4 Correct 77 ms 7596 KB Correct
5 Correct 81 ms 7508 KB Correct
6 Correct 1 ms 2392 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 66 ms 4112 KB Correct
9 Correct 66 ms 4520 KB Correct
10 Correct 45 ms 6480 KB Correct
11 Correct 14 ms 2904 KB Correct
12 Correct 48 ms 6748 KB Correct
13 Correct 73 ms 5564 KB Correct
14 Correct 71 ms 5988 KB Correct
15 Correct 66 ms 6012 KB Correct
16 Correct 76 ms 4772 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Correct
2 Correct 0 ms 2392 KB Correct
3 Correct 0 ms 2396 KB Correct
4 Correct 0 ms 2396 KB Correct
5 Incorrect 1 ms 2396 KB User solution is incorrect
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Correct
2 Correct 35 ms 5468 KB Correct
3 Incorrect 105 ms 7248 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 2392 KB Correct
2 Correct 0 ms 2392 KB Correct
3 Correct 17 ms 5468 KB Correct
4 Correct 0 ms 2396 KB Correct
5 Correct 19 ms 7000 KB Correct
6 Correct 20 ms 7220 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 0 ms 2396 KB Correct
11 Correct 21 ms 5468 KB Correct
12 Correct 6 ms 2764 KB Correct
13 Correct 77 ms 7596 KB Correct
14 Correct 81 ms 7508 KB Correct
15 Correct 1 ms 2392 KB Correct
16 Correct 0 ms 2396 KB Correct
17 Correct 66 ms 4112 KB Correct
18 Correct 66 ms 4520 KB Correct
19 Correct 45 ms 6480 KB Correct
20 Correct 14 ms 2904 KB Correct
21 Correct 48 ms 6748 KB Correct
22 Correct 73 ms 5564 KB Correct
23 Correct 71 ms 5988 KB Correct
24 Correct 66 ms 6012 KB Correct
25 Correct 76 ms 4772 KB Correct
26 Correct 0 ms 2396 KB Correct
27 Correct 0 ms 2396 KB Correct
28 Incorrect 1 ms 2396 KB User solution is incorrect
29 Halted 0 ms 0 KB -