Submission #888278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888278	2023-12-16T20:15:29 Z	asdasdqwer	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	1000 ms	21844 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	3676 KB	Output is correct
2	Correct	199 ms	3692 KB	Output is correct
3	Correct	202 ms	3688 KB	Output is correct
4	Correct	204 ms	3884 KB	Output is correct
5	Correct	199 ms	3676 KB	Output is correct
6	Correct	206 ms	3680 KB	Output is correct
7	Correct	211 ms	3696 KB	Output is correct
8	Correct	199 ms	3696 KB	Output is correct
9	Correct	180 ms	7736 KB	Output is correct
10	Correct	183 ms	7976 KB	Output is correct
11	Correct	84 ms	2900 KB	Output is correct
12	Correct	294 ms	5352 KB	Output is correct
13	Correct	399 ms	9148 KB	Output is correct
14	Correct	368 ms	12196 KB	Output is correct
15	Correct	644 ms	12588 KB	Output is correct
16	Correct	341 ms	16212 KB	Output is correct
17	Correct	530 ms	21844 KB	Output is correct
18	Execution timed out	1074 ms	11724 KB	Time limit exceeded
19	Execution timed out	1056 ms	14312 KB	Time limit exceeded
20	Correct	495 ms	21840 KB	Output is correct