Submission #1100297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100297	2024-10-13T12:55:00 Z	owieczka	Job Scheduling (CEOI12_jobs)	C++17	27 / 100	207 ms	36940 KB

jobs

#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);
}

Subtask #1

27.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	29 ms	23792 KB	Execution killed with signal 11
2	Runtime error	28 ms	23776 KB	Execution killed with signal 11
3	Runtime error	28 ms	23888 KB	Execution killed with signal 11
4	Runtime error	207 ms	30032 KB	Execution killed with signal 11
5	Runtime error	28 ms	23892 KB	Execution killed with signal 11
6	Runtime error	27 ms	23880 KB	Execution killed with signal 11
7	Runtime error	203 ms	30032 KB	Execution killed with signal 11
8	Runtime error	29 ms	23888 KB	Execution killed with signal 11
9	Partially correct	27 ms	12624 KB	Partially correct
10	Partially correct	28 ms	11104 KB	Partially correct
11	Partially correct	19 ms	9612 KB	Partially correct
12	Partially correct	36 ms	10380 KB	Partially correct
13	Partially correct	52 ms	13200 KB	Partially correct
14	Correct	89 ms	15944 KB	Output is correct
15	Runtime error	97 ms	27976 KB	Execution killed with signal 11
16	Runtime error	139 ms	35400 KB	Execution killed with signal 11
17	Correct	156 ms	22088 KB	Output is correct
18	Partially correct	134 ms	18096 KB	Partially correct
19	Runtime error	167 ms	36940 KB	Execution killed with signal 11
20	Correct	149 ms	22088 KB	Output is correct