Submission #1100307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100307		owieczka	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	205 ms	23172 KiB

jobs

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

pair<int, int> t[1'100'002];
int zli[1'100'001];
vector <int> zli2[100'100];
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] == x)
      {
         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);
}
//10 1 20
// 7 9 1 9 4 1 5 9 7 7 2 3 2 4 3 2 3 3 7 2

• Subtask 1: 100 / 100