제출 #415928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415928		snasibov05	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	49 ms	8844 KiB

tournament

#include <vector>

using namespace std;

#define pb push_back

struct range{
    int l, r;
    int idx;
    int next;
};

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

struct SegmentTree{
    vector<int> t;
    SegmentTree(int n){
        t.resize(4*n+5);
    }

    void update(int v, int tl, int tr, int idx, int val){
        if (tl == tr){
            t[v] = val;
            return;
        }

        int tm = (tl + tr) / 2;
        if (idx <= tm) update(v*2, tl, tm, idx, val);
        else update(v*2+1, tm+1, tr, idx, val);

        t[v] = t[v*2] + t[v*2+1];
    }

    int idx(int v, int tl, int tr, int k){
        if (tl == tr){
            return tl;
        }

        int tm = (tl + tr) / 2;
        if (t[v*2] >= k) return idx(v*2, tl, tm, k);
        else return idx(v*2+1, tm+1, tr, k - t[v*2]);
    }
};

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

    SegmentTree tree(n);

    for (int i = 0; i < n; ++i) {
        tree.update(1, 0, n-1, i, 1);
        cur[i] = i;
    }

    for (int i = 0; i < c; ++i) {
        for (int j = s[i]; j <= e[i]; ++j) {
            int k = cur[tree.idx(1, 0, n-1, j+1)];
            ed[idx].pb(k);
        }

        int k = cur[tree.idx(1, 0, n-1, s[i]+1)];
        cur[k] = idx;

        for (int j = s[i]+1; j <= e[i]; ++j) {
            tree.update(1, 0, n-1, j, 0);
        }
        idx++;
    }

    return idx-1;
}

void dfs(int v){
    for (auto x : ed[v]){
        dfs(x);
        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);

        int cnt = 0;

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

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

    return ans;

}

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