Submission #888279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888279	2023-12-16T20:18:49 Z	asdasdqwer	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	220 ms	27216 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;
        };

        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:24:14: warning: variable 'cmp' set but not used [-Wunused-but-set-variable]
   24 |         auto cmp=[](const pii &x, const pii &y) {
      |              ^~~
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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	3364 KB	Output is correct
2	Correct	27 ms	3360 KB	Output is correct
3	Correct	27 ms	3324 KB	Output is correct
4	Correct	26 ms	3352 KB	Output is correct
5	Correct	28 ms	3356 KB	Output is correct
6	Correct	33 ms	3364 KB	Output is correct
7	Correct	27 ms	3576 KB	Output is correct
8	Correct	26 ms	3356 KB	Output is correct
9	Correct	43 ms	7960 KB	Output is correct
10	Correct	32 ms	7900 KB	Output is correct
11	Correct	24 ms	3168 KB	Output is correct
12	Correct	51 ms	5460 KB	Output is correct
13	Correct	71 ms	9160 KB	Output is correct
14	Correct	113 ms	12316 KB	Output is correct
15	Correct	113 ms	12628 KB	Output is correct
16	Correct	166 ms	16008 KB	Output is correct
17	Correct	191 ms	21724 KB	Output is correct
18	Correct	220 ms	21328 KB	Output is correct
19	Correct	215 ms	27216 KB	Output is correct
20	Correct	190 ms	21840 KB	Output is correct