Submission #104837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104837	2019-04-09T10:42:42 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	110 ms	8800 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 >= 3 && check(allJobs, mid-2, d, n))
    {
        cout << mid -2 << "\n";
    }
    else 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 if (check(allJobs, mid + 2, d, n))
    {
        cout << mid + 2 << "\n";
       // print(allJobs, n, mid + 2);
    }
    else
    {
        cout << mid + 3 << "\n";
    }
}

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	11 ms	1532 KB	Output isn't correct
2	Incorrect	10 ms	1532 KB	Output isn't correct
3	Incorrect	12 ms	1532 KB	Output isn't correct
4	Incorrect	11 ms	1532 KB	Output isn't correct
5	Incorrect	10 ms	1532 KB	Output isn't correct
6	Incorrect	12 ms	1532 KB	Output isn't correct
7	Incorrect	15 ms	1532 KB	Output isn't correct
8	Incorrect	10 ms	1532 KB	Output isn't correct
9	Incorrect	12 ms	1532 KB	Output isn't correct
10	Incorrect	13 ms	1672 KB	Output isn't correct
11	Incorrect	13 ms	1532 KB	Output isn't correct
12	Incorrect	20 ms	2552 KB	Output isn't correct
13	Incorrect	33 ms	4584 KB	Output isn't correct
14	Incorrect	45 ms	4560 KB	Output isn't correct
15	Incorrect	68 ms	4588 KB	Output isn't correct
16	Incorrect	88 ms	8672 KB	Output isn't correct
17	Incorrect	68 ms	8672 KB	Output isn't correct
18	Incorrect	94 ms	8672 KB	Output isn't correct
19	Incorrect	110 ms	8800 KB	Output isn't correct
20	Incorrect	77 ms	8672 KB	Output isn't correct