Submission #553316

#	Time	Username	Problem	Language	Result	Execution time	Memory
553316		timreizin	Jousting tournament (IOI12_tournament)	C++17	100 / 100	568 ms	19892 KiB

tournament

#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 (stderr)

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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51