Cod sursa(job #2663971)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 27 octombrie 2020 18:19:19
Problema Partitie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const int NMAX = 300001;

int M[NMAX], P[NMAX];

ifstream f("partitie.in");
ofstream g("partitie.out");

int main()
{
    int N, D, i;
    f >> N >> D;
    for(int i = 1; i <= N; i++)
    {
        f >> M[i];
        P[i] = i;
    }
    sort(P + 1, P + N + 1, [&](int x, int y)
    {
        return M[x] < M[y];
    });
    int j = 1, nrSub = 0; ///nr maxim de valori ce pot incapea intr un segment de lungime D-1
    for(int i = 1; i <= N; i++)
    {
        while(j <= N && M[P[i]] - M[P[j]] >= D)
            j++;
        nrSub = max(nrSub, i - j + 1);
    }
    for(i = 1; i <= N; i++)
        M[P[i]] = i % nrSub + 1;
    g << nrSub << '\n';
    for(i = 1; i <= N; i++)
        g << M[i] << '\n';
    return 0;
}