Cod sursa(job #2537142)

Utilizator ptudortudor P ptudor Data 3 februarie 2020 10:05:51
Problema Partitie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,d;
pair <int,int> a[300005], sol[300005];
int k;

multiset <pair<int,int>> q;
int main()
{int i,j,p;
   in >> n >> d;
   for (i = 1; i <= n; i++)
      in >> a[i].first , a[i].second = i;
   sort(a + 1 , a + 1 + n);

   auto it = q.begin();
   for (i = 1; i <= n; i++){
      if (q.empty()){
         q.insert({a[i].first , 1});
         k = 1;
         sol[i] = {a[i].second , 1};
         continue;
      }
      it = q.begin();
      if ( a[i].first - (*it).first < d){
         k++;
         sol[i] = {a[i].second , k};
         q.insert({a[i].first , k});
         continue;
      }

      pair<int,int> x = {a[i].first - d ,1};
      it = q.lower_bound(x);
      if(it == q.end()) it--;
      if(a[i] - *it < d)
         it--;
      x = {a[i].first , (*it).second};
      q.erase(it);
      q.insert(x);

      sol[i] = {a[i].second , x.second};
   }

   out << k << "\n";
   sort(sol + 1, sol + 1 + n);
   for (i = 1; i <= n; i++)
      out << sol[i].second << " ";
   out << "\n";
  // out << k << "\n";
  return 0;
}