Cod sursa(job #2508460)

Utilizator ancaoxoxSfia Anca ancaoxox Data 12 decembrie 2019 10:58:31
Problema Partitie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("partitie.in");
ofstream cout("partitie.out");


int p[300005], cap[300005];

struct poz{
int first;
int second;
};


poz v[300005];



bool cmp1(const poz &a, const poz &b)
{
    return a.first < b.first;
}

bool cmp2(const poz &a, const poz &b)
{
    return a.second < b.second;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, d, i, q=1, j, x, cnt=1, okn=0, capmin=0;

    cin >> n >> d;

    for (i=1; i<=n; i++)
    {cin >> x;
    v[i].first=x;
    v[i].second=i;
    }

    sort(v+1, v+n+1, cmp1);



    p[v[1].second]=1;
    cap[1]=v[1].first;
    capmin=v[1].first;

    for (i=2; i<=n; i++)
    {
        okn=0;
        for (j=1; j<=cnt; j++)
        {
            if (v[i].first<capmin+d)
            {
                break;
            }
            if (v[i].first>=cap[j]+d)
            {
                if (cap[j]==capmin)
                capmin=cap[j+1];
                cap[j]=v[i].first;
                if (v[i].first<capmin)
                capmin=v[i].first;
                p[v[i].second]=j;
                okn=1;
                break;
            }
        }
        if (okn==0)
        {
            cnt++;
            cap[cnt]=v[i].first;
            p[v[i].second]=cnt;
        }
    }


    sort (v+1, v+n+1, cmp2);




 //   cout << cnt << '\n';

  //  for (i=1; i<=n; i++)
   // cout << p[v[i].second] << '\n';


    return 0;
}