Submission #583316

#	Time	Username	Problem	Language	Result	Execution time	Memory
583316		Jomnoi	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1056 ms	1988 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5005;

int table[MAX_N][12];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    vector <pair <int, int>> vec, tmp;
    for(int i = 0; i < N; i++) {
        vec.emplace_back(i, i);
    }
    for(int c = 0; c < C; c++) {
        int s = S[c], e = E[c];

        tmp.clear();
        for(int i = 0; i < s; i++) {
            tmp.push_back(vec[i]);
        }
        tmp.emplace_back(vec[s].first, vec[e].second);
        S[c] = tmp.back().first;
        E[c] = tmp.back().second;
        for(int i = e + 1; i < vec.size(); i++) {
            tmp.push_back(vec[i]);
        }
        vec = tmp;
    }

    for(int i = 0; i < N - 1; i++) {
        table[i][0] = K[i];
    }
    for(int j = 1; j < 12; j++) {
        for(int i = 0; i + (1<<j) - 1 < N; i++) {
            table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]);
        }
    }

    int max_win = -1, best_pos = 0;
    for(int p = 0; p < N; p++) {
        int cnt_win = 0;
        for(int c = 0; c < C; c++) {
            if(S[c] <= p and p <= E[c]) {
                int j = log2(E[c] - S[c]);
                int power = max(table[S[c]][j], table[E[c] - (1<<j)][j]);

                if(power < R) {
                    cnt_win++;
                }
            }
        }

        if(max_win < cnt_win) {
            max_win = cnt_win;
            best_pos = p;
        }
    }
    return best_pos;
}

Compilation message (stderr)

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

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