Submission #1085283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085283		testergml	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	559 ms	27288 KiB

jobs

#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 (stderr)

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 / 100