oj.uz

답안 #1075420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1075420 2024-08-26T05:53:41 Z GrindMachine Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 98 ms 8264 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];
	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));

	vector<char> ans(n+5);

	auto ok = [&](ll mid){
		ll mnf = inf2, mxs = -inf2;

		for(auto [x,i,t] : c){
			if(t == 1){
				// sprinkler
				if(mnf != inf2){
					if(x-mid > mnf){
						return false;
					}
					ans[i] = 'L';
					mnf = inf2;
				}
				else{
					mxs = x+mid;
					ans[i] = 'R';
				}
			}
			else{
				// flower
				if(mxs >= x) conts;
				amin(mnf,x);
			}
		}

		return mnf == inf2;
	};

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

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

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

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

int main(){
	int t = 1;
	// cin >> t;

	rep1(i,t){
		solve(i);
	}

	return 0;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 28 ms 4288 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 31 ms 4304 KB Correct
5 Correct 31 ms 4388 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 7 ms 1388 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 41 ms 4296 KB Correct
3 Correct 6 ms 1052 KB Correct
4 Correct 98 ms 8260 KB Correct
5 Correct 94 ms 8264 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 67 ms 5060 KB Correct
9 Correct 68 ms 5060 KB Correct
10 Correct 84 ms 8260 KB Correct
11 Correct 36 ms 4296 KB Correct
12 Correct 60 ms 4624 KB Correct
13 Correct 60 ms 7876 KB Correct
14 Correct 64 ms 7876 KB Correct
15 Correct 69 ms 7876 KB Correct
16 Correct 59 ms 4808 KB Correct

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 1 ms 348 KB Correct
5 Incorrect 1 ms 348 KB User solution is worse than jury's solution
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 43 ms 4488 KB Correct
3 Incorrect 96 ms 8264 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 28 ms 4288 KB Correct
4 Correct 1 ms 344 KB Correct
5 Correct 31 ms 4304 KB Correct
6 Correct 31 ms 4388 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 7 ms 1388 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 41 ms 4296 KB Correct
12 Correct 6 ms 1052 KB Correct
13 Correct 98 ms 8260 KB Correct
14 Correct 94 ms 8264 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 67 ms 5060 KB Correct
18 Correct 68 ms 5060 KB Correct
19 Correct 84 ms 8260 KB Correct
20 Correct 36 ms 4296 KB Correct
21 Correct 60 ms 4624 KB Correct
22 Correct 60 ms 7876 KB Correct
23 Correct 64 ms 7876 KB Correct
24 Correct 69 ms 7876 KB Correct
25 Correct 59 ms 4808 KB Correct
26 Correct 1 ms 344 KB Correct
27 Correct 1 ms 348 KB Correct
28 Incorrect 1 ms 348 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -