Submission #104831

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104831	2019-04-09T10:30:41 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	197 ms	20436 KB

jobs

#include <bits/stdc++.h>

using namespace std;

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

    int left = 0;
    int right = m;

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

        if (check(allJobs, mid, d, n))
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    int mid = (left+right) >> 1;

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

Compilation message

jobs.cpp: In function 'bool check(std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:12: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:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < allJobs.size(); i++)
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:41: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	19 ms	2928 KB	Output isn't correct
2	Incorrect	24 ms	2928 KB	Output isn't correct
3	Incorrect	21 ms	2908 KB	Output isn't correct
4	Incorrect	20 ms	2936 KB	Output isn't correct
5	Incorrect	21 ms	2856 KB	Output isn't correct
6	Incorrect	19 ms	3064 KB	Output isn't correct
7	Incorrect	18 ms	2936 KB	Output isn't correct
8	Incorrect	20 ms	2936 KB	Output isn't correct
9	Incorrect	32 ms	4976 KB	Output isn't correct
10	Incorrect	28 ms	4976 KB	Output isn't correct
11	Incorrect	22 ms	2416 KB	Output isn't correct
12	Incorrect	40 ms	4200 KB	Output isn't correct
13	Incorrect	100 ms	6880 KB	Output isn't correct
14	Incorrect	101 ms	8928 KB	Output isn't correct
15	Incorrect	141 ms	10576 KB	Output isn't correct
16	Incorrect	196 ms	13268 KB	Output isn't correct
17	Incorrect	146 ms	15956 KB	Output isn't correct
18	Incorrect	176 ms	16668 KB	Output isn't correct
19	Incorrect	197 ms	20436 KB	Output isn't correct
20	Incorrect	153 ms	16076 KB	Output isn't correct