Submission #1100307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100307	2024-10-13T13:24:06 Z	owieczka	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	205 ms	23172 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	7760 KB	Output is correct
2	Correct	15 ms	7760 KB	Output is correct
3	Correct	20 ms	7760 KB	Output is correct
4	Correct	27 ms	7760 KB	Output is correct
5	Correct	15 ms	7840 KB	Output is correct
6	Correct	29 ms	7704 KB	Output is correct
7	Correct	14 ms	7760 KB	Output is correct
8	Correct	15 ms	7760 KB	Output is correct
9	Correct	24 ms	8016 KB	Output is correct
10	Correct	23 ms	8016 KB	Output is correct
11	Correct	34 ms	7664 KB	Output is correct
12	Correct	41 ms	9032 KB	Output is correct
13	Correct	64 ms	12696 KB	Output is correct
14	Correct	87 ms	14216 KB	Output is correct
15	Correct	108 ms	16216 KB	Output is correct
16	Correct	129 ms	17552 KB	Output is correct
17	Correct	162 ms	20552 KB	Output is correct
18	Correct	198 ms	22344 KB	Output is correct
19	Correct	205 ms	23172 KB	Output is correct
20	Correct	158 ms	20552 KB	Output is correct