oj.uz

Submission #888280

# Submission time Handle Problem Language Result Execution time Memory
888280 2023-12-16T20:20:53 Z asdasdqwer Job Scheduling (CEOI12_jobs) C++14
100 / 100
 231 ms 27276 KB 
#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m,d;cin>>n>>d>>m;
    vector<int> a(m);
    for (int &x:a)cin>>x;
    typedef pair<int,int> pii;
    vector<vector<int>> req(n);
    for (int i=0;i<m;i++) {
        req[a[i]-1].push_back(i);
    }

    vector<int> day(m, 0);

    function<bool(int)> sim=[&](int machines) -> bool {
        typedef pair<int,int> pii;
        auto cmp=[](const pii &x, const pii &y) {
            if (x.first != y.first) return x.first > y.first;
            return x.second > y.second;
        };

        queue<pii> pq;

        for (int i=0;i<n;i++) {
            for (int x:req[i]) {
                pq.push({i+d, x});
            }

            for (int j=0;j<machines;j++) {
                if (pq.size() == 0) break;
                pii t=pq.front();pq.pop();
                if (t.first < i) return false;
                day[t.second]=i;
            }
        }

        if (pq.size()){
            return false;
        }

        return true;
    };

    int l=0, r=1e8;
    int ans=-1;
    while (l <= r) {
        int m=l+(r-l)/2;
        bool b=sim(m);
        if (b) {
            r=m-1;
            ans=m;
        }

        else {
            l=m+1;
        }
    }

    sim(ans);

    vector<vector<int>> ass(n);
    for (int i=0;i<m;i++) {
        ass[day[i]].push_back(i+1);
    }

    cout<<ans<<"\n";
    for (int i=0;i<n;i++) {
        for (int x:ass[i]) cout<<x<<" ";
        cout<<"0\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In lambda function:
jobs.cpp:21:14: warning: variable 'cmp' set but not used [-Wunused-but-set-variable]
   21 |         auto cmp=[](const pii &x, const pii &y) {
      |              ^~~
jobs.cpp: In function 'int main()':
jobs.cpp:11:27: warning: typedef 'pii' locally defined but not used [-Wunused-local-typedefs]
   11 |     typedef pair<int,int> pii;
      |                           ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3352 KB Output is correct
2 Correct 36 ms 3312 KB Output is correct
3 Correct 28 ms 3188 KB Output is correct
4 Correct 29 ms 3352 KB Output is correct
5 Correct 28 ms 3356 KB Output is correct
6 Correct 31 ms 3364 KB Output is correct
7 Correct 39 ms 3372 KB Output is correct
8 Correct 29 ms 3356 KB Output is correct
9 Correct 34 ms 7764 KB Output is correct
10 Correct 32 ms 7772 KB Output is correct
11 Correct 25 ms 2904 KB Output is correct
12 Correct 52 ms 5460 KB Output is correct
13 Correct 76 ms 9052 KB Output is correct
14 Correct 120 ms 12292 KB Output is correct
15 Correct 131 ms 12636 KB Output is correct
16 Correct 209 ms 16004 KB Output is correct
17 Correct 195 ms 21844 KB Output is correct
18 Correct 227 ms 21676 KB Output is correct
19 Correct 231 ms 27276 KB Output is correct
20 Correct 211 ms 21824 KB Output is correct