oj.uz

Submission #1075809

# Submission time Handle Problem Language Result Execution time Memory
1075809 2024-08-26T09:15:45 Z GrindMachine Sprinklers (CEOI24_sprinklers) C++17
100 / 100
 383 ms 17100 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], a[i]++;
	rep1(i,m) cin >> b[i], 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<ll> b2(m+5);
 	ll ptr = 1;
 	rep1(i,m){
 		if(b[i] != -1){
 			b2[ptr++] = b[i];
 		}
 	}

 	b = b2;
 	m = ptr-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){
		vector<ll> dp1(m+5,-inf2);
		vector<ll> last_set(m+5);
		vector<pll> par(siz+5,{-1,-1});
		dp1[0] = 0;
		ll ind = -1;
 		ll prev_ok = -1;
 		ll timer = 1;
 		pll active_val = {-1,-1};
		set<ll> active;

		for(auto [x,i,t] : c){
			ind++;
			ll mxj = 0;

			if(t == 1){
				pll mx = {-inf2,-1};
				ll first_big = lower_bound(b.begin()+1,b.begin()+m+1,a[i]-mid)-b.begin();

				{
					auto it = active.lower_bound(first_big);
					if(it != active.end()){
						ll j = *it;
						ll val = dp1[j];
						if(active_val.ss >= last_set[j]){
							val = active_val.ff;
						}
						mx = {val,j};
					}
				}

				active_val = {a[i]+mid,timer++};

				// turn right
				if(dp1[0] >= 0){
					dp1[0] = a[i]+mid;
					last_set[0] = timer++;
				}
 
				// turn left
				if(mx.ff > dp1[0]){
					dp1[0] = mx.ff;
					par[ind] = {0,mx.ss};
					last_set[0] = timer++;
				}
			}
			else{
				if(dp1[0] >= x) conts;
				dp1[i] = dp1[0];
				if(dp1[i] >= 0){
					active.insert(i);				
				}
				last_set[i] = timer++;
				dp1[0] = -inf2;
				last_set[0] = timer++;
				par[ind] = {i,0};
				mxj = i;
			}
		}
 	
 		// cout << endl << endl << endl;

		if(construct){
			ll j = 0;
			rev(ind,siz-1,0){
				if(par[ind].ff == j){
					ll j2 = par[ind].ss;
					if(c[ind][2] == 1){
						ll i = c[ind][1];
						assert(j == 0 and j2 > j);
						ans[i] = 'L';
					}
					j = j2;
				}
				else{
					if(c[ind][2] == 1){
						ll i = c[ind][1];
						ans[i] = 'R';
					}
				}
			}	
 
			assert(!j);
		}
 
		return dp1[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;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:123:7: warning: variable 'mxj' set but not used [-Wunused-but-set-variable]
  123 |    ll mxj = 0;
      |       ^~~
Main.cpp:116:7: warning: unused variable 'prev_ok' [-Wunused-variable]
  116 |    ll prev_ok = -1;
      |       ^~~~~~~

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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 41 ms 7420 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 77 ms 7444 KB Correct
5 Correct 55 ms 7364 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 420 KB Correct
8 Correct 9 ms 1736 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 64 ms 7228 KB Correct
3 Correct 17 ms 1232 KB Correct
4 Correct 232 ms 12212 KB Correct
5 Correct 248 ms 14208 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 132 ms 10372 KB Correct
9 Correct 129 ms 10484 KB Correct
10 Correct 153 ms 15800 KB Correct
11 Correct 109 ms 7840 KB Correct
12 Correct 115 ms 11760 KB Correct
13 Correct 164 ms 10660 KB Correct
14 Correct 209 ms 11704 KB Correct
15 Correct 205 ms 11816 KB Correct
16 Correct 146 ms 9228 KB Correct

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 1 ms 348 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 1 ms 444 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 2 ms 348 KB Correct
10 Correct 1 ms 344 KB Correct
11 Correct 1 ms 384 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 1 ms 348 KB Correct
14 Correct 0 ms 348 KB Correct
15 Correct 1 ms 348 KB Correct
16 Correct 1 ms 348 KB Correct
17 Correct 1 ms 348 KB Correct
18 Correct 1 ms 348 KB Correct
19 Correct 1 ms 348 KB Correct
20 Correct 1 ms 348 KB Correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 82 ms 7956 KB Correct
3 Correct 383 ms 14164 KB Correct
4 Correct 377 ms 14864 KB Correct
5 Correct 356 ms 14516 KB Correct
6 Correct 345 ms 14728 KB Correct
7 Correct 364 ms 15012 KB Correct
8 Correct 361 ms 14768 KB Correct
9 Correct 377 ms 14764 KB Correct
10 Correct 358 ms 14776 KB Correct
11 Correct 346 ms 14776 KB Correct
12 Correct 0 ms 344 KB Correct
13 Correct 1 ms 344 KB Correct
14 Correct 86 ms 6272 KB Correct
15 Correct 86 ms 6184 KB Correct
16 Correct 97 ms 6376 KB Correct
17 Correct 105 ms 8800 KB Correct
18 Correct 74 ms 8988 KB Correct
19 Correct 99 ms 9296 KB Correct
20 Correct 286 ms 14380 KB Correct
21 Correct 282 ms 14364 KB Correct
22 Correct 232 ms 12988 KB Correct
23 Correct 214 ms 13224 KB Correct
24 Correct 139 ms 11700 KB Correct
25 Correct 160 ms 11812 KB Correct
26 Correct 110 ms 5832 KB Correct
27 Correct 115 ms 5192 KB Correct
28 Correct 161 ms 10108 KB Correct
29 Correct 150 ms 8608 KB Correct
30 Correct 140 ms 11168 KB Correct
31 Correct 222 ms 15288 KB Correct

Subtask #5
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 41 ms 7420 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 77 ms 7444 KB Correct
6 Correct 55 ms 7364 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 0 ms 420 KB Correct
9 Correct 9 ms 1736 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 64 ms 7228 KB Correct
12 Correct 17 ms 1232 KB Correct
13 Correct 232 ms 12212 KB Correct
14 Correct 248 ms 14208 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 132 ms 10372 KB Correct
18 Correct 129 ms 10484 KB Correct
19 Correct 153 ms 15800 KB Correct
20 Correct 109 ms 7840 KB Correct
21 Correct 115 ms 11760 KB Correct
22 Correct 164 ms 10660 KB Correct
23 Correct 209 ms 11704 KB Correct
24 Correct 205 ms 11816 KB Correct
25 Correct 146 ms 9228 KB Correct
26 Correct 1 ms 348 KB Correct
27 Correct 1 ms 348 KB Correct
28 Correct 1 ms 348 KB Correct
29 Correct 1 ms 444 KB Correct
30 Correct 1 ms 348 KB Correct
31 Correct 1 ms 348 KB Correct
32 Correct 2 ms 348 KB Correct
33 Correct 1 ms 344 KB Correct
34 Correct 1 ms 384 KB Correct
35 Correct 1 ms 348 KB Correct
36 Correct 1 ms 348 KB Correct
37 Correct 0 ms 348 KB Correct
38 Correct 1 ms 348 KB Correct
39 Correct 1 ms 348 KB Correct
40 Correct 1 ms 348 KB Correct
41 Correct 1 ms 348 KB Correct
42 Correct 1 ms 348 KB Correct
43 Correct 1 ms 348 KB Correct
44 Correct 82 ms 7956 KB Correct
45 Correct 383 ms 14164 KB Correct
46 Correct 377 ms 14864 KB Correct
47 Correct 356 ms 14516 KB Correct
48 Correct 345 ms 14728 KB Correct
49 Correct 364 ms 15012 KB Correct
50 Correct 361 ms 14768 KB Correct
51 Correct 377 ms 14764 KB Correct
52 Correct 358 ms 14776 KB Correct
53 Correct 346 ms 14776 KB Correct
54 Correct 0 ms 344 KB Correct
55 Correct 1 ms 344 KB Correct
56 Correct 86 ms 6272 KB Correct
57 Correct 86 ms 6184 KB Correct
58 Correct 97 ms 6376 KB Correct
59 Correct 105 ms 8800 KB Correct
60 Correct 74 ms 8988 KB Correct
61 Correct 99 ms 9296 KB Correct
62 Correct 286 ms 14380 KB Correct
63 Correct 282 ms 14364 KB Correct
64 Correct 232 ms 12988 KB Correct
65 Correct 214 ms 13224 KB Correct
66 Correct 139 ms 11700 KB Correct
67 Correct 160 ms 11812 KB Correct
68 Correct 110 ms 5832 KB Correct
69 Correct 115 ms 5192 KB Correct
70 Correct 161 ms 10108 KB Correct
71 Correct 150 ms 8608 KB Correct
72 Correct 140 ms 11168 KB Correct
73 Correct 222 ms 15288 KB Correct
74 Correct 76 ms 8380 KB Correct
75 Correct 330 ms 17100 KB Correct
76 Correct 249 ms 14204 KB Correct
77 Correct 1 ms 344 KB Correct
78 Correct 124 ms 10204 KB Correct
79 Correct 126 ms 10268 KB Correct
80 Correct 204 ms 13912 KB Correct
81 Correct 109 ms 7672 KB Correct
82 Correct 104 ms 7664 KB Correct
83 Correct 89 ms 7792 KB Correct
84 Correct 42 ms 5764 KB Correct
85 Correct 188 ms 11392 KB Correct
86 Correct 254 ms 11676 KB Correct
87 Correct 229 ms 15332 KB Correct
88 Correct 48 ms 9128 KB Correct
89 Correct 47 ms 9100 KB Correct