oj.uz

답안 #740179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740179 2023-05-12T06:55:05 Z Unforgettablepl Job Scheduling (CEOI12_jobs) C++17
100 / 100
 369 ms 23464 KB 
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = INT32_MAX;
vector<pair<int,int>> jobs;
int n,d,m;

bool check(int machines, bool print){
    // machines is the amount of machines we have
    if(machines==0){return false;}
    int day = 1;
    int curr = 0;
    vector<vector<int>> schedule(n);
    for(auto&job:jobs){
        while(job.first>day){
            curr = 0;
            day++;
        }
        if(day-job.first>d){
            return false;
        }
        curr++;
        schedule[day-1].emplace_back(job.second);
        if(curr == machines){
            day++;
            curr = 0;
        }
    }
    if(print){
        cout << machines << '\n';
        for(auto&i:schedule){
            for(int&j:i){
                cout << j << ' ';
            }
            cout << "0\n";
        }
    }
    return true;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("measurement.in","r",stdin);
//    freopen("measurement.out","w",stdout);
    cin >> n >> d >> m;
    jobs.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }
    sort(all(jobs));
    int l = 1;
    int r = 1000000;
    int ans = 1000000;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid,false)){
            ans = min(ans,mid);
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    check(ans,true);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2896 KB Output is correct
2 Correct 29 ms 2876 KB Output is correct
3 Correct 29 ms 2820 KB Output is correct
4 Correct 30 ms 2948 KB Output is correct
5 Correct 29 ms 2964 KB Output is correct
6 Correct 28 ms 2896 KB Output is correct
7 Correct 28 ms 2948 KB Output is correct
8 Correct 29 ms 2912 KB Output is correct
9 Correct 38 ms 5000 KB Output is correct
10 Correct 41 ms 5072 KB Output is correct
11 Correct 36 ms 2580 KB Output is correct
12 Correct 78 ms 4960 KB Output is correct
13 Correct 104 ms 7820 KB Output is correct
14 Correct 171 ms 11124 KB Output is correct
15 Correct 187 ms 11576 KB Output is correct
16 Correct 232 ms 14868 KB Output is correct
17 Correct 281 ms 19296 KB Output is correct
18 Correct 293 ms 19568 KB Output is correct
19 Correct 369 ms 23464 KB Output is correct
20 Correct 292 ms 19208 KB Output is correct