Submission #104830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104830	2019-04-09T10:28:43 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	199 ms	20336 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(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});
    }

    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:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < allJobs.size(); i++)
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:37: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	20 ms	2844 KB	Output isn't correct
2	Incorrect	23 ms	2972 KB	Output isn't correct
3	Incorrect	21 ms	2900 KB	Output isn't correct
4	Incorrect	23 ms	2928 KB	Output isn't correct
5	Incorrect	21 ms	2936 KB	Output isn't correct
6	Incorrect	18 ms	2928 KB	Output isn't correct
7	Incorrect	19 ms	2820 KB	Output isn't correct
8	Incorrect	19 ms	2900 KB	Output isn't correct
9	Incorrect	28 ms	4856 KB	Output isn't correct
10	Incorrect	29 ms	4848 KB	Output isn't correct
11	Incorrect	23 ms	2288 KB	Output isn't correct
12	Incorrect	37 ms	4200 KB	Output isn't correct
13	Incorrect	75 ms	6932 KB	Output isn't correct
14	Incorrect	108 ms	8992 KB	Output isn't correct
15	Incorrect	113 ms	10600 KB	Output isn't correct
16	Incorrect	158 ms	13244 KB	Output isn't correct
17	Incorrect	162 ms	15956 KB	Output isn't correct
18	Incorrect	165 ms	16672 KB	Output isn't correct
19	Incorrect	199 ms	20336 KB	Output isn't correct
20	Incorrect	170 ms	15880 KB	Output isn't correct