Submission #104836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104836	2019-04-09T10:42:06 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	89 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	12 ms	1532 KB	Output isn't correct
3	Incorrect	11 ms	1532 KB	Output isn't correct
4	Incorrect	11 ms	1532 KB	Output isn't correct
5	Incorrect	11 ms	1532 KB	Output isn't correct
6	Incorrect	10 ms	1532 KB	Output isn't correct
7	Incorrect	11 ms	1532 KB	Output isn't correct
8	Incorrect	10 ms	1532 KB	Output isn't correct
9	Incorrect	11 ms	1572 KB	Output isn't correct
10	Incorrect	11 ms	1532 KB	Output isn't correct
11	Incorrect	11 ms	1532 KB	Output isn't correct
12	Incorrect	18 ms	2552 KB	Output isn't correct
13	Incorrect	31 ms	4588 KB	Output isn't correct
14	Incorrect	43 ms	4596 KB	Output isn't correct
15	Incorrect	53 ms	4712 KB	Output isn't correct
16	Incorrect	62 ms	8800 KB	Output isn't correct
17	Incorrect	84 ms	8672 KB	Output isn't correct
18	Incorrect	76 ms	8676 KB	Output isn't correct
19	Incorrect	89 ms	8676 KB	Output isn't correct
20	Incorrect	71 ms	8672 KB	Output isn't correct