oj.uz

Submission #1039621

# Submission time Handle Problem Language Result Execution time Memory
1039621 2024-07-31T06:02:16 Z 박영우(#11029) Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 22 ms 3420 KB 
//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<short, short> pss;
#define MAX 1010101
#define MAXS 20
#define INF 1'000'000'010'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define TC 0
#ifdef LOCAL
#define DEBUG(a) cout<<a
#else
#define DEBUG(...) 
#endif
int S[MAX];
int F[MAX];
int dp[2][MAX];
int ans[MAX];
int path[2][MAX];
int N, M;
int findpv(int x) {
	int ind = lower_bound(F + 1, F + M + 1, x) - F;
	ind--;
	return ind;
}
int findne(int x) {
	int ind = upper_bound(F + 1, F + M + 1, x) - F;
	return ind;
}
bool chk(int m) {
	if (S[1] - m <= F[1]) dp[0][1] = findne(S[1]);
	else dp[0][1] = 0;
	if (S[1] <= F[1]) dp[1][1] = findne(S[1] + m);
	else dp[1][1] = 1;
	path[0][1] = 0;
	path[1][1] = 1;
	int i;
	DEBUG('m' << m << ln);
	for (i = 2; i <= N; i++) {
		dp[0][i] = dp[1][i] = 0;
		if (dp[0][i - 1]) {
			if (F[dp[0][i - 1]] < S[i]) {
				dp[1][i] = dp[0][i - 1];
				path[1][i] = 0;
				if (S[i] - F[dp[0][i - 1]] <= m) {
					dp[0][i] = findne(S[i]);
					path[0][i] = 0;
				}
			}
			else {
				dp[1][i] = findne(S[i] + m);
				path[1][i] = 0;
			}
		}
		if (dp[1][i - 1]) {
			if (F[dp[1][i - 1]] < S[i]) {
				if (dp[1][i] < dp[1][i - 1]) {
					dp[1][i] = dp[1][i - 1];
					path[1][i] = 1;
				}
				if (S[i] - F[dp[0][i - 1]] <= m) {
					int nv = findne(S[i - 1] + m);
					if (dp[0][i] < nv) {
						dp[0][i] = nv;
						path[0][i] = 1;
					}
				}
			}
			else {
				int nv = findne(S[i] + m);
				if (dp[1][i] < nv) {
					dp[1][i] = nv;
					path[1][i] = 1;
				}
			}
		}
	}
	for (i = 1; i <= N; i++) DEBUG(dp[0][i] << bb);
	DEBUG(ln);
	for (i = 1; i <= N; i++) DEBUG(dp[1][i] << bb);
	DEBUG(ln);
	return (dp[0][N] > M || dp[1][N] > M);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i;
	set<int> st;
	for (i = 1; i <= N; i++) cin >> S[i], st.insert(S[i]);
	for (i = 1; i <= M; i++) {
		cin >> F[i];
		if (st.find(F[i]) != st.end()) {
			i--;
			M--;
		}
	}
	if (!M) {
		cout << "YES" << ln;
		for (i = 1; i <= N; i++) cout << 'L';
		return 0;
	}
	int l, r;
	l = 0;
	r = 1'000'000'100;
	//r = 2;
	while (r - l > 1) {
		int m = l + r >> 1;
		if (chk(m)) r = m;
		else l = m;
	}
	if (!chk(r)) {
		cout << -1;
		return 0;
	}
	cout << r << ln;
	int v = 0;
	if (dp[1][N] > M) v = 1;
	string s;
	for (i = N; i >= 1; i--) {
		if (v) s.push_back('R');
		else s.push_back('L');
		v = path[v][i];
	}
	reverse(s.begin(), s.end());
	cout << s;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:118:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 6 ms 3420 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 7 ms 1616 KB Correct
5 Correct 8 ms 1628 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 2 ms 604 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 9 ms 1624 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 22 ms 2148 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 6 ms 3420 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 7 ms 1616 KB Correct
6 Correct 8 ms 1628 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 2 ms 604 KB Correct
10 Correct 0 ms 348 KB Correct
11 Incorrect 9 ms 1624 KB User solution is worse than jury's solution
12 Halted 0 ms 0 KB -