oj.uz

답안 #515954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515954 2022-01-20T07:52:58 Z apostoldaniel854 Teams (CEOI11_tea) C++14
70 / 100
 2500 ms 53196 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6;

struct node_info {
    int mx, id;
    node_info(int value = 0, int id = 0) {
        this->mx = value;
        this->id = id;
    }
    node_info operator + (node_info other) const {
        node_info RES;
        if (mx > other.mx)
            RES = {this->mx, this->id};
        else
            RES = other;
        return RES;
    }
};

class SegTree {
private:
    vector <node_info> seg;
public:
    SegTree(int n) {
        seg.resize(1 + 4 * n);
    }
    void update_pos(int node, int lb, int rb, int pos, node_info val) {
        if (lb == rb) {
            seg[node] = val;
            return;
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (pos <= mid)
            update_pos(lnode, lb, mid, pos, val);
        else
            update_pos(rnode, mid + 1, rb, pos, val);
        seg[node] = seg[lnode] + seg[rnode];
    }
    node_info query_range(int node, int lb, int rb, int ql, int qr) {
        if (lb == ql && rb == qr)
            return seg[node];
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (ql <= mid && qr <= mid)
            return query_range(lnode, lb, mid, ql, qr);
        else if (mid + 1 <= ql && mid + 1 <= qr)
            return query_range(rnode, mid + 1, rb, ql, qr);
        else
            return query_range(lnode, lb, mid, ql, mid) + query_range(rnode, mid + 1, rb, mid + 1, qr);
    }
};

pair <int, int> a[1 + MAX_N];
int dp[1 + MAX_N];
int from[1 + MAX_N];

int n;


int get_max_teams(int limit_size) {
    SegTree D(n);
    dp[0] = 0;
    from[0] = 0;
    D.update_pos(1, 0, n, 0, node_info(dp[0], 0));
    for (int i = 1; i <= n; i++) {
        if (max(0, i - limit_size) <= i - a[i].first) {
            node_info res = D.query_range(1, 0, n, max(0, i - limit_size), i - a[i].first);
            dp[i] = res.mx + 1;
            from[i] = res.id;
        }
        else {
            dp[i] = -(1 << 30);
            from[i] = -1;
        }
        D.update_pos(1, 0, n, i, node_info(dp[i], i));
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + n + 1);
    int max_teams = get_max_teams(n);
    int lb = 1, rb = n, min_size = n;
    while (lb <= rb) {
        int mid = (lb + rb) / 2;
        if (get_max_teams(mid) == max_teams)
            min_size = mid, rb = mid - 1;
        else
            lb = mid + 1;
    }
    get_max_teams(min_size);
    cout << max_teams << "\n";
    int curr = n;
    while (curr > 0) {
        cout << curr - from[curr] << " ";
        for (int i = curr; i > from[curr]; i--)
            cout << a[i].second << " ";
        cout << "\n";
        curr = from[curr];
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 584 KB Output is correct
2 Correct 14 ms 588 KB Output is correct
3 Correct 15 ms 584 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 580 KB Output is correct
2 Correct 13 ms 556 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 4512 KB Output is correct
2 Correct 336 ms 4460 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 5064 KB Output is correct
2 Correct 305 ms 4296 KB Output is correct
3 Correct 408 ms 5060 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2542 ms 38448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2512 ms 52384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2533 ms 53196 KB Time limit exceeded
2 Halted 0 ms 0 KB -