Cod sursa(job #2658502)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 14 octombrie 2020 09:22:41
Problema Partitie Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
#define nl '\n'
using namespace std;
ifstream f ( "partitie.in" );
ofstream g ( "partitie.out" );
struct elem
{
    int val, index;
};
elem v[300001];
bool cmp ( elem a, elem b )
{
    return a.val < b.val;
}
int ans[300001];
int part[300001], nrp;
bool cautbin ( int val )
{
    int p = 1, u = nrp, ans = 0;

    while ( p <= u )
    {
        int m = ( p + u ) / 2;

        if ( part[m] <= val )
        {
            u = m - 1;
            ans = m;
        }
        else p = m + 1;
    }

    return ans;
}
int main()
{
    int N, D;
    f >> N >> D;

    for ( int i = 1; i <= N; i++ )
    {
        v[i].index = i;
        f >> v[i].val;
    }

    sort ( v + 1, v + N + 1, cmp );

    for ( int i = 1; i <= N; i++ )
    {
        int val = v[i].val;
        int poz = cautbin ( val - D );

        if ( poz == 0 )
        {
            part[++nrp] = val;
            ans[v[i].index] = nrp;
        }
        else
        {
           part[poz]=val;
           ans[v[i].index]=poz;
        }
    }

    g << nrp << nl;

    for ( int i = 1; i <= N; i++ )
        g << ans[i] << nl;

    return 0;
}