Submission #777504

#	Time	Username	Problem	Language	Result	Execution time	Memory
777504		boris_mihov	Teams (IOI15_teams)	C++17	34 / 100	4033 ms	33860 KiB

teams

#include "teams.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;

int n;
std::vector <int> v[MAXN];
void init(int N, int A[], int B[]) 
{
    n = N;
    for (int i = 0 ; i < n ; ++i)
    {
        v[A[i]].push_back(B[i]);
    }
}

std::priority_queue <int> pq;
int can(int M, int K[]) 
{
    while (!pq.empty())
    {
        pq.pop();
    }

    int ptr = 0;
    std::sort(K, K + M);
    for (int i = 0 ; i < M ; ++i)
    {
        while (ptr + 1 <= K[i])
        {
            ptr++;
            for (const int &j : v[ptr])
            {
                pq.push(-j);
            }
        }

        while (pq.size() && -pq.top() < K[i])
        {
            pq.pop();
        }

        if (pq.size() < K[i])
        {
            return 0;
        }

        for (int j = 0 ; j < K[i] ; ++j)
        {
            pq.pop();
        }
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:50:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         if (pq.size() < K[i])
      |             ~~~~~~~~~~^~~~~~

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