Submission #104834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104834	2019-04-09T10:38:29 Z	daili	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	1000 ms	8808 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++)
                     ~~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'void print(std::vector<std::pair<int, int> >&, int, int)':
jobs.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < allJobs.size(); i++)
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:41: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	442 ms	1532 KB	Unexpected end of file - int32 expected
2	Incorrect	441 ms	1532 KB	Unexpected end of file - int32 expected
3	Incorrect	528 ms	1532 KB	Unexpected end of file - int32 expected
4	Incorrect	415 ms	1532 KB	Unexpected end of file - int32 expected
5	Incorrect	460 ms	1532 KB	Unexpected end of file - int32 expected
6	Incorrect	462 ms	1532 KB	Unexpected end of file - int32 expected
7	Incorrect	572 ms	1532 KB	Unexpected end of file - int32 expected
8	Incorrect	445 ms	1532 KB	Unexpected end of file - int32 expected
9	Execution timed out	1071 ms	1532 KB	Time limit exceeded
10	Execution timed out	1067 ms	1532 KB	Time limit exceeded
11	Incorrect	77 ms	1532 KB	Unexpected end of file - int32 expected
12	Incorrect	133 ms	2704 KB	Unexpected end of file - int32 expected
13	Incorrect	164 ms	4560 KB	Unexpected end of file - int32 expected
14	Execution timed out	1073 ms	4588 KB	Time limit exceeded
15	Incorrect	316 ms	4588 KB	Unexpected end of file - int32 expected
16	Execution timed out	1081 ms	8672 KB	Time limit exceeded
17	Execution timed out	1068 ms	8808 KB	Time limit exceeded
18	Execution timed out	1076 ms	8676 KB	Time limit exceeded
19	Execution timed out	1074 ms	8676 KB	Time limit exceeded
20	Execution timed out	1081 ms	8672 KB	Time limit exceeded