Submission #104820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104820	2019-04-09T10:10:38 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	260 ms	20012 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;
        }
    }

    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
    {
        cout << mid + 1 << "\n";
        print(allJobs, n, mid + 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	37 ms	2928 KB	Output isn't correct
2	Incorrect	26 ms	2928 KB	Output isn't correct
3	Incorrect	28 ms	2932 KB	Output isn't correct
4	Incorrect	34 ms	2928 KB	Output isn't correct
5	Incorrect	20 ms	2928 KB	Output isn't correct
6	Incorrect	21 ms	3064 KB	Output isn't correct
7	Incorrect	25 ms	2928 KB	Output isn't correct
8	Incorrect	28 ms	2928 KB	Output isn't correct
9	Incorrect	40 ms	4848 KB	Output isn't correct
10	Incorrect	37 ms	4848 KB	Output isn't correct
11	Incorrect	29 ms	2328 KB	Output isn't correct
12	Incorrect	71 ms	4200 KB	Output isn't correct
13	Incorrect	98 ms	6868 KB	Output isn't correct
14	Incorrect	148 ms	8664 KB	Output isn't correct
15	Incorrect	161 ms	10208 KB	Output isn't correct
16	Incorrect	237 ms	12620 KB	Output isn't correct
17	Incorrect	213 ms	15444 KB	Output isn't correct
18	Incorrect	240 ms	16340 KB	Output isn't correct
19	Incorrect	260 ms	20012 KB	Output isn't correct
20	Incorrect	228 ms	15452 KB	Output isn't correct