oj.uz

Submission #553316

# Submission time Handle Problem Language Result Execution time Memory
553316 2022-04-25T12:22:04 Z timreizin Jousting tournament (IOI12_tournament) C++17
100 / 100
 568 ms 19892 KB 
#include <vector>
#include <list>
#include <iterator>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T, class C = less<>>
using ordered_set = tree<T, null_type, C, rb_tree_tag, tree_order_statistics_node_update>;

struct cell
{
    int i, l, r;

    cell(int i, int l, int r) : i(i), l(l), r(r)
    {}
};

struct cmp
{
    bool operator()(list<cell>::iterator a, list<cell>::iterator b)
    {
        return a->i < b->i;
    }
};

void convert(int n, vector<pair<int, int>> &rounds)
{
    list<cell> cells;
    for (int i = 0; i < n; ++i) cells.emplace_back(i, i, i);
    ordered_set<list<cell>::iterator, cmp> help;
    for (auto it = cells.begin(); it != cells.end(); ++it) help.insert(it);
    for (auto &[l, r] : rounds)
    {
        auto itL = *help.find_by_order(l), itR = *help.find_by_order(r);
        r = itL->r = itR->r;
        l = itL->l;
        for (auto i = itR; i != itL; --i)
        {
            help.erase(i);
            i = cells.erase(i);
        }
    }
}

int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
    vector<int> ranks(n - 1);
    for (int i = 0; i < n - 1; ++i) ranks[i] = K[i];
    vector<pair<int, int>> rounds(c);
    for (int i = 0; i < c; ++i) rounds[i] = {S[i], E[i]};
    convert(n, rounds);
    vector<pair<vector<int>, vector<int>>> se(n);
    for (int i = 0; i < rounds.size(); ++i)
    {
        se[rounds[i].first].first.push_back(i);
        se[rounds[i].second].second.push_back(i);
    }
    set<int> lose;
    ordered_set<int> win;
    pair<int, int> res{0, 0};
    for (int p = 0; p < n; ++p)
    {
        for (int i : se[p].first)
        {
            bool isWin = true;
            for (int j = rounds[i].first; j < rounds[i].second; ++j) isWin = isWin && (ranks[j] < r);
            if (isWin) win.insert(i);
            else lose.insert(i);
        }
        int last = n + 1;
        if (!lose.empty()) last = *lose.begin();
        res = max(res, {win.order_of_key(last), -p});
        for (int i : se[p].second)
        {
            lose.erase(i);
            win.erase(i);
        }
    }
    return -res.second;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < rounds.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct
7 Correct 7 ms 1012 KB Output is correct
8 Correct 6 ms 1236 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 7 ms 1236 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9616 KB Output is correct
2 Correct 446 ms 16304 KB Output is correct
3 Correct 101 ms 12636 KB Output is correct
4 Correct 267 ms 19892 KB Output is correct
5 Correct 399 ms 14620 KB Output is correct
6 Correct 171 ms 18892 KB Output is correct
7 Correct 568 ms 15268 KB Output is correct
8 Correct 363 ms 15172 KB Output is correct
9 Correct 94 ms 12620 KB Output is correct
10 Correct 103 ms 12644 KB Output is correct