Submission #888278

#	Time	Username	Problem	Language	Result	Execution time	Memory
888278		asdasdqwer	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	1074 ms	21844 KiB

jobs

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse4")

#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;
        };

        priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);

        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.top();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 (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:14:27: warning: typedef 'pii' locally defined but not used [-Wunused-local-typedefs]
   14 |     typedef pair<int,int> pii;
      |                           ^~~

• Subtask 1: 90 / 100