oj.uz

답안 #899718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899718 2024-01-06T22:46:01 Z Karoot Job Scheduling (CEOI12_jobs) C++17
100 / 100
 333 ms 22868 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 1e5+1;

vector<int> v[MAXN];
vector<int> schedule[MAXN];
int n, d, m; 

bool isPossible(int machines){
    queue<pair<int, int> > q;
    for (int i = 0; i < n; i++){
        schedule[i].clear();
        for (int x : v[i])q.push({x, i+d});
        for (int j = 0; j < machines && !q.empty(); j++){
            int node = q.front().first;
            int t = q.front().second;
            q.pop();
            schedule[i].push_back(node);
            if (t < i)return false;
        }
    }
    return true;
}

int main(){
    scoobydoobydoo();
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++){
        int a; cin >> a;
        v[--a].push_back(i+1);
    }

    int a = 1, b = 1000001;
    int ret = -1;
    while (a < b){
        int k = (a+b)>>1;
        if (isPossible(k)){
            b = k;
            ret = k;
        } else {
            a = k+1;
        }
    }


    isPossible(ret);

    cout << ret << endl;
    for (int i = 0; i < n; i++){
        for (int x : schedule[i])cout << x << " ";
        cout << 0 << endl;
    }







    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 8160 KB Output is correct
2 Correct 31 ms 7900 KB Output is correct
3 Correct 32 ms 7896 KB Output is correct
4 Correct 40 ms 7764 KB Output is correct
5 Correct 43 ms 7840 KB Output is correct
6 Correct 40 ms 7904 KB Output is correct
7 Correct 37 ms 7900 KB Output is correct
8 Correct 44 ms 7916 KB Output is correct
9 Correct 128 ms 7284 KB Output is correct
10 Correct 135 ms 7256 KB Output is correct
11 Correct 24 ms 7248 KB Output is correct
12 Correct 50 ms 9216 KB Output is correct
13 Correct 74 ms 12300 KB Output is correct
14 Correct 96 ms 15028 KB Output is correct
15 Correct 97 ms 15624 KB Output is correct
16 Correct 172 ms 18468 KB Output is correct
17 Correct 152 ms 22788 KB Output is correct
18 Correct 169 ms 21324 KB Output is correct
19 Correct 333 ms 22824 KB Output is correct
20 Correct 273 ms 22868 KB Output is correct