Submission #888277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888277	2023-12-16T20:07:20 Z	asdasdqwer	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	1000 ms	40496 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

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=1e9;
    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:13:27: warning: typedef 'pii' locally defined but not used [-Wunused-local-typedefs]
   13 |     typedef pair<int,int> pii;
      |                           ^~~

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	6968 KB	Output is correct
2	Correct	281 ms	7184 KB	Output is correct
3	Correct	285 ms	6996 KB	Output is correct
4	Correct	264 ms	7532 KB	Output is correct
5	Correct	279 ms	6988 KB	Output is correct
6	Correct	269 ms	6988 KB	Output is correct
7	Correct	284 ms	6996 KB	Output is correct
8	Correct	268 ms	6972 KB	Output is correct
9	Correct	190 ms	9860 KB	Output is correct
10	Correct	205 ms	9992 KB	Output is correct
11	Correct	108 ms	5108 KB	Output is correct
12	Correct	333 ms	9728 KB	Output is correct
13	Correct	425 ms	16784 KB	Output is correct
14	Correct	574 ms	22168 KB	Output is correct
15	Correct	657 ms	22972 KB	Output is correct
16	Correct	606 ms	29316 KB	Output is correct
17	Runtime error	805 ms	40496 KB	Memory limit exceeded
18	Execution timed out	1069 ms	25092 KB	Time limit exceeded
19	Execution timed out	1057 ms	28928 KB	Time limit exceeded
20	Runtime error	790 ms	40324 KB	Memory limit exceeded