제출 #1100297

#제출 시각아이디문제언어결과실행 시간메모리
1100297owieczkaJob Scheduling (CEOI12_jobs)C++17
27 / 100
207 ms36940 KiB
#include <bits/stdc++.h>
using namespace std;

pair<int, int> t[1'000'002];
int zli[1'000'001];
vector <int> zli2[100'002];
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++;
      }
      while (st_free < t[i].first)
      {
         st_free++;
      }
      zli[st_free]++;
      zli2[st_free].push_back(t[i].second);
   }
   for (int i = 1; i <= n; i++)
   {
      for (auto j : zli2[i])
      {
         cout << j << ' ';
      }
      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);
}
#Verdict Execution timeMemoryGrader output
Fetching results...