Submission #104835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104835	2019-04-09T10:40:11 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	96 ms	8740 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});
    }

    /*for (int i = 1; i <= m; i++)
    {
        if (check(allJobs, i, d, n))
        {
            cout << i << "\n";
            print(allJobs, n, i);
            return 0;
        }
    }*/

    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++)
                     ~~^~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	1532 KB	Output isn't correct
2	Incorrect	14 ms	1532 KB	Output isn't correct
3	Incorrect	13 ms	1532 KB	Output isn't correct
4	Incorrect	12 ms	1532 KB	Output isn't correct
5	Incorrect	16 ms	1532 KB	Output isn't correct
6	Incorrect	12 ms	1444 KB	Output isn't correct
7	Incorrect	17 ms	1532 KB	Output isn't correct
8	Incorrect	15 ms	1508 KB	Output isn't correct
9	Incorrect	15 ms	1532 KB	Output isn't correct
10	Incorrect	15 ms	1716 KB	Output isn't correct
11	Incorrect	14 ms	1532 KB	Output isn't correct
12	Incorrect	25 ms	2552 KB	Output isn't correct
13	Incorrect	32 ms	4644 KB	Output isn't correct
14	Incorrect	65 ms	4640 KB	Output isn't correct
15	Incorrect	72 ms	4744 KB	Output isn't correct
16	Incorrect	75 ms	8740 KB	Output isn't correct
17	Incorrect	89 ms	8672 KB	Output isn't correct
18	Incorrect	87 ms	8676 KB	Output isn't correct
19	Incorrect	96 ms	8672 KB	Output isn't correct
20	Incorrect	63 ms	8680 KB	Output isn't correct