Submission #375203

#	Time	Username	Problem	Language	Result	Execution time	Memory
375203		jhwest2	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1086 ms	12512 KiB

tournament

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 2e5 + 10;

int n, c, r, K[MAX], S[MAX], E[MAX], Par[MAX], Dp[MAX], Dep[MAX];
vector<int> G[MAX];

void update(int a) {
    K[a] = 0;
    for (int x : G[a]) K[a] = max(K[a], K[x]);
}
int GetBestPosition(int N, int C, int R, int *k, int *s, int *e) {
    n = N; c = C; r = R; K[0] = r;
    for (int i = 1; i < n; i++) K[i] = k[i - 1];
    for (int i = 0; i < c; i++) S[i] = s[i], E[i] = e[i];

    vector<int> V; int p = 0;
    for (int i = 0; i < c; i++) {
        while (V.size() <= E[i]) V.push_back(p++);
        while (V.size() > S[i]) Par[V.back()] = n, V.pop_back();
        V.push_back(n++);
    }
    for (int i = 0; i < n - 1; i++) {
        G[Par[i]].push_back(i); K[Par[i]] = max(K[Par[i]], K[i]);
    }
    for (int i = n - 2; i >= 0; i--) {
        if (K[Par[i]] == K[i]) Dp[i] = Dp[Par[i]] + 1;
        Dep[i] = Dep[Par[i]] + 1;
    }

    for (int j = 0; j < n; j++) cout << Dp[j] << ' ';
    cout << '\n';

    pint ans = { -1, -1 }; vector<int> W;
    for (int i = 0; i < n - c - 1; i++) {
        ans = max(ans, { Dp[i], -i }); swap(K[i], K[i + 1]);
        int x = i, y = i + 1;
        if (Dep[x] < Dep[y]) swap(x, y);
        W.push_back(x); W.push_back(y);
        while (Dep[x] > Dep[y] && Par[x] != Par[y]) {
            update(Par[x]), x = Par[x], W.push_back(x);
        }
        while (Par[x] != Par[y]) {
            update(Par[x]); update(Par[y]);
            x = Par[x]; y = Par[y];
            W.push_back(x); W.push_back(y);
        }


        while (!W.empty()) {
            int u = W.back(); W.pop_back();
            if (K[Par[u]] == K[u]) Dp[u] = Dp[Par[u]] + 1;
            else Dp[u] = 0;
        }
    }
    ans = max(ans, { Dp[n - c - 1], 1 + c - n });
    return -ans.vb;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:24:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |         while (V.size() <= E[i]) V.push_back(p++);
      |                ~~~~~~~~~^~~~~~~
tournament.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         while (V.size() > S[i]) Par[V.back()] = n, V.pop_back();
      |                ~~~~~~~~~^~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51