Submission #1069970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069970		faruk	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	1050 ms	13292 KiB

Main

#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 (!inorder.count(*eve.me))
            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];
    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 < m; i++)
        if (!to_del[i])
            newf.push_back(flowe[i]);
    flowe = newf;
    m = newf.size();
    
    string poopie = "asd";
    int l = 0, r = 1e9, 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 (stderr)

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:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 0; i < flowe.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47