oj.uz

답안 #903892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
903892 2024-01-11T13:30:59 Z absolutePi Job Scheduling (CEOI12_jobs) C++17
100 / 100
 563 ms 29264 KB 
#include <bits/stdc++.h>

using namespace std;

int n,d,m;

pair<bool,vector<vector<int>>> works(vector<pair<int,int>> &jobs,int machines){
    int temp=0;
    vector<vector<int>> schedule(n);
    for(int day=1;day<=n;day++){
        for(int mac=0;mac<machines;mac++){
            if(jobs[temp].first>day){
                break;
            }
            if(jobs[temp].first+d>=day){
                schedule[day-1].push_back(jobs[temp++].second);
            }
            else{
                return {false,schedule};
            }
            if(temp==m){return {true,schedule};}
        }
    }
    return {false,schedule};
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin >> n >> d >> m;
    vector<pair<int,int>> jobs(m);
    for(int i=0;i<m;i++){
        int day;
        cin >> day;
        //date,index
        jobs[i] = {day,i+1};
    }
    sort(jobs.begin(),jobs.end());
    vector<vector<int>> ans;
    int l=0,r=m,mid;
    while(l<r){
        mid = l+(r-l)/2;
        pair<bool,vector<vector<int>>> res = works(jobs,mid);
        if(res.first){
            r=mid;
            ans = res.second;
        }
        else{
            l=mid+1;
        }
    }
    cout << l << endl;
    for(int i=0;i<n;i++){
        for(auto j : ans[i]){
            cout << j << ' ';
        }
        cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 3340 KB Output is correct
2 Correct 46 ms 3376 KB Output is correct
3 Correct 44 ms 3480 KB Output is correct
4 Correct 50 ms 3472 KB Output is correct
5 Correct 48 ms 3480 KB Output is correct
6 Correct 64 ms 3468 KB Output is correct
7 Correct 43 ms 3392 KB Output is correct
8 Correct 43 ms 3364 KB Output is correct
9 Correct 186 ms 10072 KB Output is correct
10 Correct 206 ms 10260 KB Output is correct
11 Correct 40 ms 3204 KB Output is correct
12 Correct 89 ms 5624 KB Output is correct
13 Correct 125 ms 9788 KB Output is correct
14 Correct 211 ms 12752 KB Output is correct
15 Correct 208 ms 12644 KB Output is correct
16 Correct 304 ms 18500 KB Output is correct
17 Correct 369 ms 21932 KB Output is correct
18 Correct 378 ms 21172 KB Output is correct
19 Correct 563 ms 29264 KB Output is correct
20 Correct 361 ms 21660 KB Output is correct