# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1039700 |
2024-07-31T07:54:59 Z |
라스무스 뷘터(#11030) |
Sprinklers (CEOI24_sprinklers) |
C++17 |
|
2000 ms |
3676 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<lint> a(n), b(m);
for (auto &x : a)
cin >> x;
a.insert(a.begin(), -2e9);
a.insert(a.begin(), 3e9);
n = sz(a);
for (auto &x : b)
cin >> x;
auto trial = [&](lint x) {
vector<vector<pi>> attach(n + 1);
vector<int> Lmax(n + 1, -1), Rmax(n + 1, n + 1);
for (int i = 0; i < m; i++) {
if (binary_search(all(a), b[i]))
continue;
int p0 = lower_bound(all(a), b[i] - x) - a.begin();
int p1 = lower_bound(all(a), b[i]) - a.begin();
int p2 = upper_bound(all(a), b[i] + x) - a.begin();
if (p0 == p1 && p1 == p2)
return string();
if (p0 < p1 && p1 < p2)
attach[p1].push_back({p0, p2});
else if (p0 < p1) {
// [p0 .. p1) is not all L
Lmax[p1] = max(Lmax[p1], p0);
} else if (p1 < p2) {
// [p1 .. p2) is not all R
Rmax[p1] = min(Rmax[p1], p2);
}
}
for (int i = 1; i <= n; i++) {
Lmax[i] = max(Lmax[i], Lmax[i - 1]);
}
for (int i = n - 1; i >= 0; i--)
Rmax[i] = min(Rmax[i], Rmax[i + 1]);
vector<int> dp(n + 1);
dp[0] = 1;
vector<pi> trace(n + 1);
for (int i = 1; i < n; i++) {
sort(all(attach[i]));
for (int j = Lmax[i] + 1; j < i; j++) {
for (int k = i + 1; k < Rmax[i]; k++) {
if (!binary_search(all(attach[i]), pi{j, k}) && dp[j]) {
dp[k] = 1;
trace[k] = pi{j, i};
}
}
}
}
if (!dp[n])
return string();
string ans(n, '0');
for (int i = n; i; i = trace[i][0]) {
for (int j = trace[i][0]; j < trace[i][1]; j++)
ans[j] = 'L';
for (int j = trace[i][1]; j < i; j++)
ans[j] = 'R';
}
ans = ans.substr(1, n - 2);
return ans;
};
int s = 0, e = 1e9 + 69;
// int s = 1000, e = 1000;
while (s != e) {
int m = (s + e) / 2;
if (sz(trial(m)))
e = m;
else
s = m + 1;
}
if (s > int(1e9))
cout << "-1\n";
else {
cout << s << "\n";
cout << trial(s) << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Incorrect |
30 ms |
1112 KB |
User solution is worse than jury's solution |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Execution timed out |
2102 ms |
3508 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Incorrect |
1 ms |
344 KB |
User solution is incorrect |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Execution timed out |
2041 ms |
3676 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Incorrect |
30 ms |
1112 KB |
User solution is worse than jury's solution |
4 |
Halted |
0 ms |
0 KB |
- |