Submission #104882

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104882	2019-04-09T12:36:31 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	318 ms	13780 KB

jobs

#include <bits/stdc++.h>

using namespace std;

bool check(int x, int n, vector<pair<int,int>> &allJobs, bool finall, int m, int d)
{
  int ptr = 1;
  for(int i = 1; i <= n;i++)
  {
      int ct = 0;
      while(ptr <= m && allJobs[ptr].first <= i && ct < x)
      {
          if(allJobs[ptr].first + d >= i)
          {
              ptr++;
          }
          else
          {
              return false;
          }
          if(finall)
          {
              cout << allJobs[ptr-1].second << " ";
          }
          ct++;
      }
      if(finall)
      {
          cout << 0 << "\n";
      }
  }
  if(ptr <= m)
  {
    return false;
  }
  return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d, m;
    cin >> n >> d >> m;

    vector<pair<int,int>> allJobs;
    allJobs.push_back({0, 0});
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        allJobs.push_back({x, i+1});
    }

    sort(allJobs.begin(), allJobs.end());

    int left = 0;
    int right = m;

    while(left < right)
    {
        int mid = (left + right) >> 1;

        if (check(mid, n, allJobs, 0, m, d))
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    cout << left << "\n";
    auto z = check(left, n, allJobs, 1, m, d);
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:75:10: warning: unused variable 'z' [-Wunused-variable]
     auto z = check(left, n, allJobs, 1, m, d);
          ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1908 KB	Output is correct
2	Correct	38 ms	1900 KB	Output is correct
3	Correct	26 ms	2032 KB	Output is correct
4	Correct	34 ms	1904 KB	Output is correct
5	Correct	23 ms	1904 KB	Output is correct
6	Correct	25 ms	1904 KB	Output is correct
7	Correct	23 ms	1912 KB	Output is correct
8	Correct	26 ms	1912 KB	Output is correct
9	Correct	42 ms	2028 KB	Output is correct
10	Correct	41 ms	2028 KB	Output is correct
11	Correct	40 ms	1940 KB	Output is correct
12	Correct	85 ms	3304 KB	Output is correct
13	Correct	113 ms	4832 KB	Output is correct
14	Correct	134 ms	6252 KB	Output is correct
15	Correct	157 ms	7732 KB	Output is correct
16	Correct	217 ms	9300 KB	Output is correct
17	Correct	251 ms	10744 KB	Output is correct
18	Correct	288 ms	12256 KB	Output is correct
19	Correct	318 ms	13780 KB	Output is correct
20	Correct	302 ms	10708 KB	Output is correct