#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct node {
bool is_spr;
int pos, id;
node() {}
node(bool is_spr, int pos, int id) : is_spr(is_spr), pos(pos), id(id) {}
bool operator<(const node &b) const {
if (pos == b.pos)
return id < b.id;
return pos < b.pos;
}
};
struct myevent {
set<node>::iterator me;
bool is_l;
myevent() {}
myevent(bool is_l, set<node>::iterator me) : is_l(is_l), me(me) {}
};
bool cmp(pair<int, set<node>::iterator> a, pair<int, set<node>::iterator> b)
{
return a.first < b.first;
}
string out;
queue<myevent> events;
set<node> inorder;
set<pair<int, set<node>::iterator>, decltype(cmp)*> ballset(cmp);
void upd(set<node>::iterator to_rem) {
if (!to_rem->is_spr)
return;
if (to_rem == prev(inorder.end()))
events.push(myevent(true, to_rem));
else if (next(to_rem)->is_spr) {
events.push(myevent(true, to_rem));
events.push(myevent(false, next(to_rem)));
} else if (to_rem == inorder.begin()) {
events.push(myevent(false, to_rem));
}
}
void rem(set<node>::iterator to_rem) {
if (!to_rem->is_spr)
ballset.erase(ballset.find(mp(to_rem->pos, to_rem)));
auto prv = prev(to_rem);
bool upprv = false;
if (to_rem != inorder.begin())
upprv = true;
inorder.erase(to_rem);
if (upprv)
upd(prv);
}
void process_event(myevent eve, int f) {
int lb, rb;
if (eve.is_l)
lb = eve.me->pos - f, out[eve.me->id] = 'L';
else
lb = eve.me->pos, out[eve.me->id] = 'R';
rb = lb + f;
rem(eve.me);
auto rbp = ballset.upper_bound(mp(rb, inorder.begin()));
if (rbp != ballset.end() and rbp->first == rb)
rbp = next(rbp);
vector<set<pair<int, set<node>::iterator> >::iterator > tr;
for (auto pnt = ballset.lower_bound(mp(lb, inorder.begin())); pnt != rbp; pnt = next(pnt))
tr.push_back(pnt);
for (auto guy : tr)
rem(guy->second);
}
bool try_val(int f, vector<int> spr, vector<int> flo) {
out = string(spr.size(), '0');
inorder = set<node>();
ballset.clear();
events = queue<myevent>();
for (int i = 0; i < spr.size(); i++)
inorder.insert(node(true, spr[i], i));
for (int i = 0; i < flo.size(); i++) {
auto pnt = inorder.insert(node(false, flo[i], i)).first;
ballset.insert(mp(flo[i], pnt));
}
for (auto pnt = inorder.begin(); pnt != inorder.end(); pnt = next(pnt))
upd(pnt);
while (!events.empty()) {
myevent eve = events.front(); events.pop();
if (out[eve.me->pos] != '0')
continue;
process_event(eve, f);
}
vector<pii> sprink;
flo.clear();
for (auto guy : inorder)
{
if (guy.is_spr)
sprink.push_back(mp(guy.pos, guy.id));
else
flo.push_back(guy.pos);
}
if (flo.empty())
return true;
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
set<int> sproing;
vector<int> flowe(m), spri(n);
for (int i = 0; i < n; i++)
cin >> spri[i];
for (int i = 0; i < m; i++)
cin >> flowe[i];
sort(all(flowe));
flowe.erase(unique(all(flowe)), flowe.end());
sproing = set<int>(all(spri));
vector<bool> to_del(m);
for (int i = 0; i < flowe.size(); i++)
if (sproing.count(flowe[i]))
to_del[i] = true;
vector<int> newf;
for (int i = 0; i < flowe.size(); i++)
if (!to_del[i])
newf.push_back(flowe[i]);
flowe = newf;
m = newf.size();
string poopie = "asd";
int l = 0, r = 1e9 + 1, ans = -1;
while (l < r) {
int mid = (l + r) / 2;
if (try_val(mid, spri, flowe))
ans = mid, r = mid, poopie = out;
else
l = mid + 1;
}
cout << ans << "\n";
if (ans != -1)
cout << poopie << "\n";
}
Compilation message
Main.cpp: In constructor 'myevent::myevent(bool, std::set<node>::iterator)':
Main.cpp:26:10: warning: 'myevent::is_l' will be initialized after [-Wreorder]
26 | bool is_l;
| ^~~~
Main.cpp:25:25: warning: 'std::set<node>::iterator myevent::me' [-Wreorder]
25 | set<node>::iterator me;
| ^~
Main.cpp:29:5: warning: when initialized here [-Wreorder]
29 | myevent(bool is_l, set<node>::iterator me) : is_l(is_l), me(me) {}
| ^~~~~~~
Main.cpp: In function 'bool try_val(int, std::vector<int>, std::vector<int>)':
Main.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 0; i < spr.size(); i++)
| ~~^~~~~~~~~~~~
Main.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < flo.size(); i++) {
| ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < flowe.size(); i++)
| ~~^~~~~~~~~~~~~~
Main.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int i = 0; i < flowe.size(); i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Correct |
| 2 |
Runtime error |
35 ms |
18504 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
User solution is worse than jury's solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
