oj.uz

Submission #1075701

# Submission time Handle Problem Language Result Execution time Memory
1075701 2024-08-26T08:42:58 Z GrindMachine Sprinklers (CEOI24_sprinklers) C++17
17 / 100
 561 ms 1048576 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,n) a[i]++;
	rep1(i,m) b[i]++;

	// sort(a.begin()+1,a.begin()+n+1);
	// sort(b.begin()+1,b.begin()+m+1);

	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));
	ll siz = sz(c);

	vector<char> ans(n+5,'?');

	auto ok = [&](ll mid, bool construct){
		ll dp[siz+5][m+5];
		pii par[siz+5][m+5];
		memset(dp,-0x3f,sizeof dp);
		memset(par,-1,sizeof par);
		dp[0][0] = 0;

		rep(i,siz){
			auto [x,ind,t] = c[i];
			if(t == 1){
				pll mx = {-inf2,-1};

				rep1(j,m){
					if(b[j] > x) break;
					if(dp[i][j] < 0) conts;

					if(b[j] >= x-mid){
						pll px = {dp[i][j],j};
						amax(mx,px);
					}

					dp[i+1][j] = x+mid;
					par[i+1][j] = {j,2};
				}

				// turn right
				if(dp[i][0] >= 0){
					dp[i+1][0] = x+mid;
					par[i+1][0] = {0,2};
				}

				// turn left
				if(mx.ff > dp[i+1][0]){
					dp[i+1][0] = mx.ff;
					par[i+1][0] = {mx.ss,1};
				}
			}
			else{
				rep1(j,m){
					dp[i+1][j] = dp[i][j];
					par[i+1][j] = {j,0};
				}

				if(dp[i][0] >= x){
					dp[i+1][0] = dp[i][0];
					par[i+1][0] = {0,0};
				}
				else{
					dp[i+1][ind] = dp[i][0];
					par[i+1][ind] = {0,0};
				}
			}
		}

		if(construct){
			ll j = 0;
			rev(i,siz,0){
				auto [j2,put] = par[i][j];
				if(put == 1){
					ans[c[i-1][1]] = 'L';
				}
				else if(put == 2){
					ans[c[i-1][1]] = 'R';
				}

				j = j2;
			}
		}

		return dp[siz][0] >= 0;
	};

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

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

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

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

	rep1(i,m){
		if(b[i] == -1) conts;
		ll x = b[i];
		bool good = false;
		rep1(j,n){
			ll l = -1, r = -1;
			if(ans[j] == 'R'){
				l = a[j], r = a[j]+best;
			}
			else{
				l = a[j]-best, r = a[j];
			}

			if(l <= x and x <= r){
				good = true;
				break;
			}
		}

		if(!good){
			assert(0);
		}
	}
}

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

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Runtime error 540 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Runtime error 538 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 15 ms 4440 KB Correct
4 Correct 11 ms 2648 KB Correct
5 Correct 62 ms 16220 KB Correct
6 Correct 60 ms 16268 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 62 ms 16220 KB Correct
9 Correct 64 ms 16220 KB Correct
10 Correct 61 ms 16292 KB Correct
11 Correct 1 ms 604 KB Correct
12 Correct 77 ms 16436 KB Correct
13 Correct 63 ms 16216 KB Correct
14 Correct 5 ms 1884 KB Correct
15 Correct 18 ms 5572 KB Correct
16 Correct 26 ms 7672 KB Correct
17 Correct 32 ms 7516 KB Correct
18 Correct 17 ms 4956 KB Correct
19 Correct 71 ms 16220 KB Correct
20 Correct 67 ms 16220 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Runtime error 561 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Runtime error 540 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -