Submission #63293

#	Time	Username	Problem	Language	Result	Execution time	Memory
63293		Kubalionzzale	Teams (IOI15_teams)	C++14	34 / 100	4022 ms	92372 KiB

teams

#include "teams.h"

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

std::vector< std::vector<int> > vec(500010);
int n;

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

int can(int m, int a[]) {

    int sum = 0;

    for (int i = 0; i < m; ++i)
    {
        sum += a[i];
        if (sum > n)
        {
            return 0;
        }
    }

    std::sort(a, a + m);
    std::multiset<int> set;
    int last = 0;

    for (int i = 0; i < m; ++i)
    {
        for (int k = last + 1; k <= a[i]; ++k)
        {
            for (int j = 0; j < vec[k].size(); ++j)
            {
                set.insert(vec[k][j]);
            }
        }

        last = a[i];

        for (auto it = set.begin(); it != set.end();)
        {
            if (*it < a[i])
                it = set.erase(it);
            else
                break;
        }


        int howMany = a[i];
        if (set.size() < howMany)
            return 0;

        int cnt = 0;
        for (auto it = set.begin(); it != set.end() && cnt < howMany; ++cnt)
        {
            it = set.erase(it);
        }
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < vec[k].size(); ++j)
                             ~~^~~~~~~~~~~~~~~
teams.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (set.size() < howMany)
             ~~~~~~~~~~~^~~~~~~~~

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