oj.uz

답안 #592353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592353 2022-07-09T04:42:53 Z Noble_Mushtak Job Scheduling (CEOI12_jobs) C++14
100 / 100
 173 ms 28280 KB 
//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

bool possible(vector<vector<num>> &jobs, num D, num M) {
    num N = sz(jobs);
    vector<num> jobsLeft(N);
    num idx = 0;
    REPI(i, N) {
        if (idx+D < i) return false;
        
        jobsLeft[i] = sz(jobs[i]);
        num spent = 0;
        while (spent < M) {
            if (idx > i) break;
            num canSpend = min(M-spent, jobsLeft[idx]);
            jobsLeft[idx] -= canSpend;
            spent += canSpend;
            if (jobsLeft[idx] == 0) ++idx;
        }
    }
    while ((idx < N) && (jobsLeft[idx] == 0)) ++idx;
    return (idx == N);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    num N, D, M;
    cin >> N >> D >> M;
    vector<vector<num>> jobs(N);
    REPI(i, M) {
        num x;
        cin >> x;
        --x;
        jobs[x].push_back(i+1);
    }
    num lo = 1, hi = M;
    while (lo < hi) {
        num mid = (lo+hi) >> 1;
        if (possible(jobs, D, mid)) hi = mid;
        else lo = mid+1;
    }

    queue<num> jobsPending;
    vector<vector<num>> ans(N);
    REPI(i, N) {
        for (num job : jobs[i]) jobsPending.push(job);
        REPI(j, lo) {
            if (jobsPending.empty()) break;
            num curJob = jobsPending.front();
            jobsPending.pop();
            ans[i].push_back(curJob);
        }
    }
    cout << lo << "\n";
    REPI(i, N) {
        for (num job : ans[i]) cout << job << " ";
        cout << "0\n";
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 4304 KB Output is correct
2 Correct 15 ms 4304 KB Output is correct
3 Correct 15 ms 4252 KB Output is correct
4 Correct 20 ms 4228 KB Output is correct
5 Correct 15 ms 4224 KB Output is correct
6 Correct 15 ms 4212 KB Output is correct
7 Correct 19 ms 4336 KB Output is correct
8 Correct 20 ms 4304 KB Output is correct
9 Correct 23 ms 8160 KB Output is correct
10 Correct 25 ms 8144 KB Output is correct
11 Correct 16 ms 3028 KB Output is correct
12 Correct 31 ms 5668 KB Output is correct
13 Correct 47 ms 10712 KB Output is correct
14 Correct 78 ms 13728 KB Output is correct
15 Correct 76 ms 13240 KB Output is correct
16 Correct 112 ms 17012 KB Output is correct
17 Correct 140 ms 25544 KB Output is correct
18 Correct 124 ms 23244 KB Output is correct
19 Correct 173 ms 28280 KB Output is correct
20 Correct 135 ms 25464 KB Output is correct