oj.uz

답안 #888279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888279 2023-12-16T20:18:49 Z asdasdqwer Job Scheduling (CEOI12_jobs) C++14
100 / 100
 220 ms 27216 KB 
#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

# 결과 실행 시간 메모리 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