Submission #480510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480510	2021-10-16T17:00:48 Z	imaginary_unit	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	718 ms	19888 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

int n, d, m, temp;
vector<vector<int> > a(100'001);

bool ok(int mch)
{
    priority_queue<int, vector<int>, greater<int> > pq;
    for(int i=1; i<=n; i++){
        for(int j=0; j<a[i].size(); j++){
            pq.push(i+d);
        }
        for(int j=0; j<mch; j++){
            if(pq.empty()){
                break;
            }
            if(pq.top() < i){
                return 0;
            }
            pq.pop();
        }
    }
    return 1;
}

int minMachines(int l, int r)
{
    while(r-l>1){
        int m=(l+r)/2;
        if(ok(m)){
            r=m;
        }
        else{
            l=m;
        }
    }
    return r;
}

int main()
{
    //freopen("angry.in", "r", stdin);
    //freopen("angry.out", "w", stdout);

    scanf("%d %d %d", &n, &d, &m);
    for(int i=1; i<=m; i++){
        scanf("%d", &temp);
        a[temp].push_back(i);
    }
    int ans=minMachines(1, m);
    cout << ans << '\n';
    vector<vector<int> > tasks(n+1);
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    for(int i=1; i<=n; i++){
        for(int j=0; j<a[i].size(); j++){
            pq.push({i+d, a[i][j]});
        }
        for(int j=0; j<ans; j++){
            if(pq.empty()){
                break;
            }
            tasks[i].push_back(pq.top().se);
            pq.pop();
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<tasks[i].size(); j++){
            cout << tasks[i][j] << ' ';
        }
        cout << 0 << '\n';
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'bool ok(int)':
jobs.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int j=0; j<a[i].size(); j++){
      |                      ~^~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j=0; j<a[i].size(); j++){
      |                      ~^~~~~~~~~~~~
jobs.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j=0; j<tasks[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~
jobs.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d", &temp);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	5220 KB	Output is correct
2	Correct	82 ms	5232 KB	Output is correct
3	Correct	88 ms	5260 KB	Output is correct
4	Correct	77 ms	5304 KB	Output is correct
5	Correct	90 ms	5216 KB	Output is correct
6	Correct	87 ms	5236 KB	Output is correct
7	Correct	91 ms	5224 KB	Output is correct
8	Correct	87 ms	5232 KB	Output is correct
9	Correct	95 ms	6980 KB	Output is correct
10	Correct	111 ms	6980 KB	Output is correct
11	Correct	64 ms	4344 KB	Output is correct
12	Correct	185 ms	6164 KB	Output is correct
13	Correct	219 ms	8900 KB	Output is correct
14	Correct	386 ms	11176 KB	Output is correct
15	Correct	298 ms	10804 KB	Output is correct
16	Correct	307 ms	13252 KB	Output is correct
17	Correct	492 ms	17864 KB	Output is correct
18	Correct	665 ms	17148 KB	Output is correct
19	Correct	718 ms	19888 KB	Output is correct
20	Correct	479 ms	17988 KB	Output is correct