Submission #104815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104815	2019-04-09T10:05:18 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	289 ms	20120 KB

jobs

#include <bits/stdc++.h>

using namespace std;

bool check(vector<pair<int,int>> &allJobs, int currNr, int delay, int days)
{
    vector<int> busy(days+1);
    for (int i = 0; i < allJobs.size(); i++)
    {
        int day = allJobs[i].first;
        while(busy[day] >= currNr)
        {
            day++;
        }
        if (allJobs[i].second + delay <= day)
        {
          return false;
        }
        else
        {
            busy[day]++;
        }
    }
    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;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        allJobs.push_back({x, i+1});
    }
    sort(allJobs.begin(), allJobs.end());

    int left = 1;
    int right = m;

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

        if (check(allJobs, mid, d, n))
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    if (check(allJobs, (left+right) >> 1, d, n))
    {
      cout << ((left+right) >> 1) << "\n";
      print(allJobs, n, (left+right) >> 1);
    }
    else
    {
        cout << ((left + right) >> 1) + 1 << "\n";
        print(allJobs, n, ((left+right) >> 1) + 1);
    }
}

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:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < allJobs.size(); i++)
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:33:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(busy[day].size() >= nr)
             ~~~~~~~~~~~~~~~~~^~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	23 ms	2936 KB	Output isn't correct
2	Incorrect	29 ms	2928 KB	Output isn't correct
3	Incorrect	36 ms	2928 KB	Output isn't correct
4	Incorrect	24 ms	2836 KB	Output isn't correct
5	Incorrect	37 ms	2916 KB	Output isn't correct
6	Incorrect	25 ms	2940 KB	Output isn't correct
7	Incorrect	22 ms	2908 KB	Output isn't correct
8	Incorrect	23 ms	2928 KB	Output isn't correct
9	Incorrect	35 ms	4852 KB	Output isn't correct
10	Incorrect	48 ms	4824 KB	Output isn't correct
11	Incorrect	28 ms	2216 KB	Output isn't correct
12	Incorrect	61 ms	4132 KB	Output isn't correct
13	Incorrect	118 ms	6676 KB	Output isn't correct
14	Incorrect	156 ms	8860 KB	Output isn't correct
15	Incorrect	150 ms	10192 KB	Output isn't correct
16	Incorrect	213 ms	12692 KB	Output isn't correct
17	Incorrect	289 ms	15320 KB	Output isn't correct
18	Incorrect	272 ms	16272 KB	Output isn't correct
19	Incorrect	282 ms	20120 KB	Output isn't correct
20	Incorrect	236 ms	15480 KB	Output isn't correct