oj.uz

Submission #1070025

# Submission time Handle Problem Language Result Execution time Memory
1070025 2024-08-22T11:05:19 Z faruk Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 1728 ms 27164 KB 
#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 {
    list<node>::iterator me;
    bool is_l;
    int id;

    myevent() {}
    myevent(bool is_l, list<node>::iterator me, int id) : is_l(is_l), me(me), id(id) {}
};

bool cmp(pair<int, list<node>::iterator> a, pair<int, list<node>::iterator> b)
{
    return a.first < b.first;
}

string out;
queue<myevent> events;
list<node> inorder;
set<pair<int, list<node>::iterator>, decltype(cmp)*> ballset(cmp);

void upd(list<node>::iterator to_rem) {
    if (!to_rem->is_spr)
        return;
    if (to_rem == prev(inorder.end()))
        events.push(myevent(true, to_rem, to_rem->id));
    if (next(to_rem) != inorder.end() and next(to_rem)->is_spr) {
        events.push(myevent(true, to_rem, to_rem->id));
        events.push(myevent(false, next(to_rem), next(to_rem)->id));
    }
    if (to_rem == inorder.begin()) {
        events.push(myevent(false, to_rem, to_rem->id));
    }
}

void rem(list<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, list<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.clear();
    ballset.clear();
    events = queue<myevent>();
    
    vector<node> nods;

    for (int i = 0; i < spr.size(); i++)
        nods.push_back(node(true, spr[i], i));
    for (int i = 0; i < flo.size(); i++) {
        nods.push_back(node(false, flo[i], i));
        //nods.insert(mp(flo[i], pnt));
    }
    sort(all(nods));
    for (int i = 0; i < nods.size(); i++)
    {
        inorder.push_back(nods[i]);
        auto pnt = prev(inorder.end());
        if (!nods[i].is_spr)
            ballset.insert(mp(nods[i].pos, 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.id] != '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::__cxx11::list<node>::iterator, int)':
Main.cpp:26:10: warning: 'myevent::is_l' will be initialized after [-Wreorder]
   26 |     bool is_l;
      |          ^~~~
Main.cpp:25:26: warning:   'std::__cxx11::list<node>::iterator myevent::me' [-Wreorder]
   25 |     list<node>::iterator me;
      |                          ^~
Main.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     myevent(bool is_l, list<node>::iterator me, int id) : is_l(is_l), me(me), id(id) {}
      |     ^~~~~~~
Main.cpp: In function 'bool try_val(int, std::vector<int>, std::vector<int>)':
Main.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < spr.size(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < flo.size(); i++) {
      |                     ~~^~~~~~~~~~~~
Main.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < nods.size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < flowe.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int i = 0; i < flowe.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 568 ms 10088 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 715 ms 13940 KB Correct
5 Correct 711 ms 14132 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 114 ms 3192 KB Correct
9 Correct 1 ms 344 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 618 ms 9556 KB Correct
3 Correct 82 ms 2336 KB Correct
4 Correct 1722 ms 27164 KB Correct
5 Correct 1728 ms 27144 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 632 ms 15944 KB Correct
9 Correct 648 ms 16348 KB Correct
10 Correct 982 ms 23584 KB Correct
11 Correct 375 ms 13324 KB Correct
12 Correct 961 ms 17988 KB Correct
13 Correct 887 ms 21080 KB Correct
14 Correct 1112 ms 23312 KB Correct
15 Correct 1185 ms 24076 KB Correct
16 Correct 626 ms 16076 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Incorrect 3 ms 348 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 568 ms 9168 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 568 ms 10088 KB Correct
4 Correct 1 ms 344 KB Correct
5 Correct 715 ms 13940 KB Correct
6 Correct 711 ms 14132 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 114 ms 3192 KB Correct
10 Correct 1 ms 344 KB Correct
11 Correct 618 ms 9556 KB Correct
12 Correct 82 ms 2336 KB Correct
13 Correct 1722 ms 27164 KB Correct
14 Correct 1728 ms 27144 KB Correct
15 Correct 1 ms 348 KB Correct
16 Correct 1 ms 348 KB Correct
17 Correct 632 ms 15944 KB Correct
18 Correct 648 ms 16348 KB Correct
19 Correct 982 ms 23584 KB Correct
20 Correct 375 ms 13324 KB Correct
21 Correct 961 ms 17988 KB Correct
22 Correct 887 ms 21080 KB Correct
23 Correct 1112 ms 23312 KB Correct
24 Correct 1185 ms 24076 KB Correct
25 Correct 626 ms 16076 KB Correct
26 Incorrect 3 ms 348 KB User solution is worse than jury's solution
27 Halted 0 ms 0 KB -