oj.uz

Submission #104883

# Submission time Handle Problem Language Result Execution time Memory
104883 2019-04-09T12:39:05 Z daili Job Scheduling (CEOI12_jobs) C++14
100 / 100
 734 ms 20052 KB 
#include <bits/stdc++.h>

using namespace std;

bool check(vector<pair<int,int>> &allJobs, int currNr, int delay, int days)
{
    vector<int> used(days+1);
    for (int i = 0; i < allJobs.size(); i++)
    {
        int currentDay = allJobs[i].first;
        while(used[currentDay] >= currNr)
        {
            currentDay++;
        }
        if (currentDay > allJobs[i].first + delay)
        {
            return false;
        }
        used[currentDay]++;
    }
    return true;
}


void print(vector<pair<int,int>> &allJobs, int days, int nr)
{
  vector<vector<int>> busy(days+1);
  for (int i = 0; i < allJobs.size(); i++)
  {
      int day = allJobs[i].first;
      while(busy[day].size() >= nr)
      {
          day++;
      }
      busy[day].push_back(allJobs[i].second);
  }
  for (int i = 1; i <= days; i++)
  {
    for (auto j: busy[i])
    {
      cout << j << " ";
    }
    cout << 0 << "\n";
  }
}

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(allJobs, mid, d, n))
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    cout << left << "\n";
    print(allJobs, n, left);
}

Compilation message

jobs.cpp: In function 'bool check(std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:8:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < allJobs.size(); i++)
                     ~~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'void print(std::vector<std::pair<int, int> >&, int, int)':
jobs.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < allJobs.size(); i++)
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:31:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(busy[day].size() >= nr)
             ~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2928 KB Output is correct
2 Correct 28 ms 2668 KB Output is correct
3 Correct 23 ms 2672 KB Output is correct
4 Correct 40 ms 2576 KB Output is correct
5 Correct 32 ms 2672 KB Output is correct
6 Correct 34 ms 2648 KB Output is correct
7 Correct 28 ms 2668 KB Output is correct
8 Correct 39 ms 2824 KB Output is correct
9 Correct 49 ms 4844 KB Output is correct
10 Correct 54 ms 4916 KB Output is correct
11 Correct 35 ms 2288 KB Output is correct
12 Correct 115 ms 4300 KB Output is correct
13 Correct 116 ms 6672 KB Output is correct
14 Correct 734 ms 9184 KB Output is correct
15 Correct 185 ms 9852 KB Output is correct
16 Correct 220 ms 12032 KB Output is correct
17 Correct 277 ms 15956 KB Output is correct
18 Correct 282 ms 16340 KB Output is correct
19 Correct 347 ms 20052 KB Output is correct
20 Correct 315 ms 15956 KB Output is correct