Cod sursa(job #2924050)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 23 septembrie 2022 18:59:03
Problema Partitie Scor Ascuns
Compilator cpp-64 Status waiting
Runda Arhiva de probleme Marime 1.04 kb
#include <algorithm>
#include <queue>
#include <fstream>

using namespace std;

ifstream fin("partitie.in");
ofstream fout("partitie.out");

const int MAXN = 300001;
pair <int, int> v[MAXN];
int vans[MAXN];
int main()
{
    int n, d, i, grupe = 1;

    fin >> n >> d;
    for(i = 1; i <= n; i++)
        fin >> v[i].first, v[i].second = i;

    sort(v + 1, v + n + 1);
    priority_queue <pair <int, int>> pq;

    pq.push({-v[1].first, 1});
    vans[v[1].second] = 1;
    for(i = 2; i <= n; i++)
    {
        if(v[i].first + pq.top().first < d)///diferenta dintre elemntul minim si elementul curent
        {
            grupe++;
            pq.push({-v[i].first, grupe});
            vans[v[i].second] = grupe;
        }
        else
        {
            int grupa = pq.top().second;
            pq.pop();
            pq.push({-v[i].first, grupa});
            vans[v[i].second] = grupa;
        }
    }
    fout << grupe << '\n';
    for(i = 1; i <= n; i++)
        fout << vans[i] << '\n';

    return 0;
}