답안 #104834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104834 2019-04-09T10:38:29 Z daili Job Scheduling (CEOI12_jobs) C++14
0 / 100
1000 ms 8808 KB
#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)
             ~~~~~~~~~~~~~~~~~^~~~~
# 결과 실행 시간 메모리 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