Submission #528346

#	Time	Username	Problem	Language	Result	Execution time	Memory
528346		Cyanmond	팀들 (IOI15_teams)	C++17	13 / 100	4074 ms	22276 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::pair<int, int>> teams;
    {
        for (int i = 0; i < M; ++i) {
            if (i == 0 or K[i] != K[i - 1]) {
                teams.push_back({K[i], 1});
            } else {
                ++teams.back().second;
            }
        }
    }

    std::vector<int> values;
    values.reserve(teams.size() + 1);
    for (const auto &[a, b] : teams) values.push_back(a);
    values.push_back(N + 1);
    const int L = (int)values.size();
    // L : sqrt(N) ?
    std::vector<std::vector<int>> people(L + 1, std::vector<int>(L + 1));
    
    // naive
    std::vector<int> prd(N + 2);
    for (int i = 0; i < L; ++i) {
        int l = i == 0 ? 1 : (values[i - 1] + 1);
        for (int j = l; j <= values[i]; ++j) prd[j] = i;
    }
    

    for (int i = 0; i < N; ++i) ++people[prd[A[i]]][prd[B[i] + 1]];
    
    std::vector<int> data(L + 1);
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j <= L; ++j) data[j] += people[i][j];
        while (teams[i].second--) {
            int c = teams[i].first;
            for (int j = i + 1; j <= L; ++j) {
                if (c > data[j]) {
                    c -= data[j];
                    data[j] = 0;
                } else {
                    data[j] -= c;
                    c = 0;
                    break;
                }
            }
            if (c != 0) return 0;
        }
    }
    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: 0 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23