Submission #528335

#	Time	Username	Problem	Language	Result	Execution time	Memory
528335		Cyanmond	Teams (IOI15_teams)	C++17	34 / 100	4073 ms	32700 KiB

teams

// clang-format off
#include <bits/stdc++.h>

int N;
std::vector<int> A, B;

void init(int n, int a[], int b[]) {
    N = n;
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; ++i) {
        A[i] = a[i];
        B[i] = b[i];
    }
}

int internal_can(const int M, std::vector<int> K) {
    int sum = 0;
    // overflow
    for (int i = 0; i < M; ++i) {
        sum += K[i];
        if (sum > N) return 0;
    }

    std::sort(K.begin(), K.end());
    std::vector<std::vector<int>> event_a(N + 1);
    for (int i = 0; i < N; ++i) event_a[A[i]].push_back(B[i] + 1);
    std::vector<int> event_q(N + 1);
    for (int i = 0; i < M; ++i) ++event_q[K[i]];

    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int i = 1; i <= N; ++i) {
        for (const int r : event_a[i]) pq.push(r);
        while (event_q[i]--) {
            int c = i;
            while (c--) {
                while ((not pq.empty()) and pq.top() <= i) pq.pop();
                if (pq.empty()) return 0;
                pq.pop();
            }
        }
    }
    return 1;
}

int can(int M, int K[]) {
    std::vector<int> k(M);
    for (int i = 0; i < M; ++i) k[i] = K[i];
    return internal_can(M, k);
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23