Submission #696428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
696428	2023-02-06T13:19:31 Z	cfjason	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	10604 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, d, m;
    cin >> n >> d >> m;
    vector<vector<int>> requestsByDay(n);
    for (int i = 0; i < m; i++)
    {
        int day;
        cin >> day;
        requestsByDay[day-1].push_back(i+1);
    }
    int lower = 0, upper = m+1;
    while (lower + 1 < upper)
    {
        int mid = (lower + upper) / 2;
        int reqIndex = 0;
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> line;
        bool valid = true;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < requestsByDay[i].size(); j++)
                line.push(array<int, 2>{i, requestsByDay[i][j]});
            for (int j = 0; j < mid; j++)
            {
                if (line.size())
                {
                    if (i - line.top()[0] > d)
                    {
                        valid = false;
                        break;
                    }
                    line.pop();
                }
                else
                {
                    break;
                }
            }
            if (!valid)
                break;
        }
        if (line.size())
            valid = false;

        if(valid){
            upper = mid;
        }
        else{
            lower = mid;
        }
    }
    cout << upper << endl;
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> line;
    int mid = upper;
    for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < requestsByDay[i].size(); j++)
                line.push(array<int, 2>{i, requestsByDay[i][j]});
            for (int j = 0; j < mid; j++)
            {
                if (line.size())
                {
                    cout << to_string(line.top()[1]) << " ";
                    line.pop();
                }
                else
                {
                    break;
                }
            }
            cout << "0" << endl;
        }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main(int, const char**)':
jobs.cpp:27:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for (int j = 0; j < requestsByDay[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:22:13: warning: unused variable 'reqIndex' [-Wunused-variable]
   22 |         int reqIndex = 0;
      |             ^~~~~~~~
jobs.cpp:63:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int j = 0; j < requestsByDay[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	211 ms	3376 KB	Output is correct
2	Correct	209 ms	3272 KB	Output is correct
3	Correct	226 ms	3404 KB	Output is correct
4	Correct	225 ms	3304 KB	Output is correct
5	Correct	206 ms	3304 KB	Output is correct
6	Correct	232 ms	3368 KB	Output is correct
7	Correct	213 ms	3312 KB	Output is correct
8	Correct	206 ms	3328 KB	Output is correct
9	Correct	288 ms	4224 KB	Output is correct
10	Correct	282 ms	4272 KB	Output is correct
11	Correct	118 ms	1416 KB	Output is correct
12	Correct	340 ms	3080 KB	Output is correct
13	Correct	449 ms	4616 KB	Output is correct
14	Correct	520 ms	6836 KB	Output is correct
15	Correct	696 ms	6732 KB	Output is correct
16	Correct	581 ms	8616 KB	Output is correct
17	Correct	878 ms	10576 KB	Output is correct
18	Execution timed out	1093 ms	5192 KB	Time limit exceeded
19	Execution timed out	1091 ms	7140 KB	Time limit exceeded
20	Correct	838 ms	10604 KB	Output is correct