Submission #415807

#	Time	Username	Problem	Language	Result	Execution time	Memory
415807		snasibov05	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1088 ms	5688 KiB

tournament

#include <vector>

using namespace std;

#define pb push_back

vector<int> val;
vector<vector<int>> ed;

int buildTree(int n, int c, int*& s, int*& e){
    int idx = n;
    vector<int> cur;

    for (int i = 0; i < n; ++i) {
        cur.pb(i);
    }

    for (int i = 0; i < c; ++i) {
        for (int j = s[i]; j <= e[i]; ++j){
            ed[idx].pb(cur[j]);
        }
        vector<int> arr;
        for (int j = 0; j < s[i]; ++j) {
            arr.pb(cur[j]);
        }
        arr.pb(idx);
        for (int j = e[i]+1; j < cur.size(); ++j) {
            arr.pb(cur[j]);
        }

        cur = arr;
        idx++;
    }

    return idx-1;
}

void dfs(int v, int pr){
    for (auto x : ed[v]){
        if (x == pr) continue;
        dfs(x, v);
        val[v] = max(val[v], val[x]);
    }
}

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
    val.resize(2*n);
    ed.resize(2*n);

    int m = buildTree(n, c, s, e);

    int mx = 0, ans = 0;

    for (int i = 0; i < n; ++i) {
        val.assign(2*n+1, 0);
        for (int j = 0; j < i; ++j) {
            val[j] = k[j];
        }
        val[i] = r;
        for (int j = i; j < n-1; ++j) {
            val[j+1] = k[j];
        }

        dfs(m, -1);

        int cnt = 0;

        for (int j = 0; j <= m; ++j) {
            if (val[j] == r) cnt++;
        }

        if (cnt > mx) {
            ans = i;
            mx = cnt;
        }
    }

    return ans;

}

Compilation message (stderr)

tournament.cpp: In function 'int buildTree(int, int, int*&, int*&)':
tournament.cpp:27:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int j = e[i]+1; j < cur.size(); ++j) {
      |                              ~~^~~~~~~~~~~~

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