Submission #1100283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100283		owieczka	Job Scheduling (CEOI12_jobs)	C++17	19 / 100	200 ms	21324 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

pair<int, int> t[1'000'002];
int zli[1'000'001];
int n, m, d;
bool war(int x)
{
   int st_free = 1;
   for (int i = 1; i <= n; i++)
   {
      zli[i] = 0;
   }
   for (int i = 1; i <= m; i++)
   {
      while (st_free < t[i].first || zli[st_free] == x)
      {
         st_free++;
      }
      zli[st_free]++;
      if (st_free - t[i].first > d)
      {
         return false;
      }
   }
   return true;
}

void ans(int x)
{
   int st_free = 1;
   for (int i = 1; i <= n; i++)
   {
      zli[i] = 0;
   }
   for (int i = 1; i <= m; i++)
   {
      if (zli[st_free] == d)
      {
         st_free++;
         cout << "0\n";
      }
      while (st_free < t[i].first)
      {
         st_free++;
         cout << "0\n";
      }
      zli[st_free]++;
      cout << t[i].second << ' ';
   }
   for (; st_free <= n; st_free++)
   {
      cout << "0\n";
   }
}

int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   cin >> n >> d >> m;
   for (int i = 1; i <= m; i++)
   {
      cin >> t[i].first;
      t[i].second = i;
   }
   sort (t+1, t + m+1);
   int beg = 1;
   int en = m;
   while (beg < en)
   {
      int x = (beg + en)/2;
      if (war(x))
      {
         en = x;
      }
      else
      {
         beg = x + 1;
      }
   }
   cout << en << '\n';
   ans(en);
}

• Subtask 1: 19 / 100