oj.uz

Submission #1085283

# Submission time Handle Problem Language Result Execution time Memory
1085283 2024-09-07T20:39:19 Z testergml Job Scheduling (CEOI12_jobs) C++14
100 / 100
 559 ms 27288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define _ ios_base::sync_with_stdio(false);cin.tie(0); 
#define endl '\n' 
#define f first 
#define s second 
#define pb push_back
#define int long long

typedef long long ll;
typedef pair<int,int> ii;
 
const int INF = 0x3f3f3f3f3f3f3f3fll;

int N, D, M;
vector<ii> jobs;
bool check(int pday) {
    vector<int> start(2*N, 0), end(2*N, 0);
    for(auto [t, i] : jobs) start[--t]++, end[t+D]++;
    int cur = 0, done = 0;
    for(int i = 0; i < 2*N; i++) {
        cur += start[i];
        done = (done + min(pday, cur));
        cur = max(0ll, cur - pday);
        done -= end[i];
        if(done < 0) return false;
    }
    return true;
}

// (CEOI) Job Scheduling
int32_t main() { _
    cin >> N >> D >> M;
    for(int i = 0; i < M; i++) {
        int t; cin >> t;
        jobs.pb({t, i+1});
    } 
    sort(jobs.begin(), jobs.end());
    int l = 1, r = M;
    while(l != r) {
        int m = (l + r) / 2;
        if(check(m)) r = m;
        else l = m + 1;
    }
    int ans = l;
    cout << ans << endl;
    queue<int> q;
    for(int t = 1, aux = 0; t <= N; t++) {
        while(aux < M && jobs[aux].f == t) q.push(jobs[aux++].s);
        for(int i = 0; i < ans; i++) if(!q.empty()) {
            cout << q.front() << ' '; q.pop();
        }
        cout << 0 << endl;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(long long int)':
jobs.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [t, i] : jobs) start[--t]++, end[t+D]++;
      |              ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 3536 KB Output is correct
2 Correct 518 ms 3536 KB Output is correct
3 Correct 530 ms 3536 KB Output is correct
4 Correct 511 ms 3740 KB Output is correct
5 Correct 559 ms 3540 KB Output is correct
6 Correct 549 ms 3744 KB Output is correct
7 Correct 510 ms 3748 KB Output is correct
8 Correct 554 ms 3732 KB Output is correct
9 Correct 518 ms 5484 KB Output is correct
10 Correct 518 ms 5444 KB Output is correct
11 Correct 20 ms 3032 KB Output is correct
12 Correct 41 ms 5568 KB Output is correct
13 Correct 61 ms 9936 KB Output is correct
14 Correct 100 ms 11580 KB Output is correct
15 Correct 109 ms 13640 KB Output is correct
16 Correct 137 ms 19440 KB Output is correct
17 Correct 157 ms 19868 KB Output is correct
18 Correct 179 ms 21856 KB Output is correct
19 Correct 288 ms 27288 KB Output is correct
20 Correct 161 ms 19864 KB Output is correct