oj.uz

답안 #102685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102685 2019-03-26T18:28:23 Z popovicirobert 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 227 ms 42284 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;

struct Fenwick {
    VI aib;
    int n;
    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }
    inline void clr() {
        fill(aib.begin(), aib.end(), 0);
    }
    inline void update(int pos, int val) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }
    inline int query(int pos) {
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }
    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
    inline int kth(int k) {
        int res = 0, cnt = 0;
        for(int step = 1 << 17; step; step >>= 1) {
            if(res + step <= n && cnt + aib[res + step] < k) {
                res += step;
                cnt += aib[res];
            }
        }
        return res + 1;
    }
};

void dfs(int nod, VVI &g, VI &idl, VI &idr, VI &lvl, int n) {
    idl[nod] = n + 1, idr[nod] = 0;
    for(auto it : g[nod]) {
        lvl[it] = lvl[nod] + 1;
        dfs(it, g, idl, idr, lvl, n);
        idl[nod] = min(idl[nod], idl[it]), idr[nod] = max(idr[nod], idr[it]);
    }
    if(nod <= n) {
        idl[nod] = idr[nod] = nod;
    }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    Fenwick fen; fen.init(N);
    for(int i = 1; i <= N; i++) {
        fen.update(i, 1);
    }

    VVI g(N + C + 1); VI id(N + 1);
    iota(id.begin(), id.end(), 0);
    VVI anc(N + C + 1, VI(18));

    int cur = N;
    for(int i = 0; i < C; i++) {
        S[i]++, E[i]++, cur++;

        int aux = fen.kth(S[i]);
        for(int j = S[i]; j <= E[i]; j++) {
            int pos = fen.kth(S[i]);
            fen.update(pos, -1);

            g[cur].push_back(id[pos]);
            anc[id[pos]][0] = cur;

        }
        fen.update(aux, 1);
        id[aux] = cur;
    }

    for(int bit = 1; bit <= 17; bit++) {
        for(int i = 1; i <= cur; i++) {
            anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }
    }

    VI idl(cur + 1), idr(cur + 1), lvl(cur + 1);

    for(int i = cur; i >= 1; i--) {
        if(lvl[i] == 0) {
            dfs(i, g, idl, idr, lvl, N);
        }
    }

    fen.clr();
    for(int i = 2; i <= N; i++) {
        fen.update(i, (K[i - 2] > R));
    }

    int ans, mx = -1;
    for(int i = 1; i <= N; i++) {
        int nod = i;
        for(int bit = 17; bit >= 0; bit--) {
            int cur = anc[nod][bit];
            if(cur > 0 && fen.sum(idl[cur], idr[cur]) == 0) {
                nod = cur;
            }
        }

        if(mx < lvl[i] - lvl[nod]) {
            mx = lvl[i] - lvl[nod], ans = i;
        }

        if(i < N) {
            if(K[i - 1] > R) {
                fen.update(i + 1, -1);
                fen.update(i, 1);
            }
        }
    }
    return ans - 1;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:125:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans - 1;
                  ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 9 ms 2304 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 10 ms 2168 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct
7 Correct 9 ms 2304 KB Output is correct
8 Correct 14 ms 2176 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 9 ms 2176 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 13304 KB Output is correct
2 Correct 226 ms 42284 KB Output is correct
3 Correct 69 ms 17396 KB Output is correct
4 Correct 187 ms 37240 KB Output is correct
5 Correct 205 ms 37752 KB Output is correct
6 Correct 180 ms 27488 KB Output is correct
7 Correct 227 ms 38904 KB Output is correct
8 Correct 222 ms 38776 KB Output is correct
9 Correct 76 ms 16240 KB Output is correct
10 Correct 93 ms 17400 KB Output is correct