Submission #1088533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088533	2024-09-14T14:57:15 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	113 ms	23376 KB

jobs

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

const int maxn = 1e5 + 10;

int n,d,m;
vector<int> v[maxn],resp[maxn];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> d >> m;
    
    for(int i = 1;i <= m;i++){
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    
    int l = 1,r = m;
    while(l <= r){
        int mid = (l + r) >> 1;
        bool check = 1;
        int pos_dia = 1,qtd = 0;
        for(int i = 1;i <= n && check;i++){
            int val = (int) v[i].size();
            if(pos_dia < i){
                pos_dia = i;
                qtd = 0;
            }
            while(val){
                if(pos_dia - i > d){
                    check = 0;
                    break;
                }
                val--;
                qtd++;
                if(qtd == mid){
                    qtd = 0;
                    pos_dia++;
                }
            }
        }
        if(check) r = mid - 1;
        else l = mid + 1;
    }
    
    cout << l << "\n";
    
    int pos_dia = 1,qtd = 0;
    for(int i = 1;i <= n;i++){
        if(pos_dia < i){
            pos_dia = i;
            qtd = 0;
        }
        while(v[i].size()){
            qtd++;
            resp[pos_dia].push_back(v[i].back());
            v[i].pop_back();
            if(qtd == l){
                qtd = 0;
                pos_dia++;
            }
        }
    }
    
    for(int i = 1;i <= n;i++){
        for(int j : resp[i])
            cout << j << " ";
        cout << 0 << "\n";
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	6872 KB	Output is correct
2	Correct	14 ms	7132 KB	Output is correct
3	Correct	13 ms	6876 KB	Output is correct
4	Correct	13 ms	6876 KB	Output is correct
5	Correct	14 ms	7128 KB	Output is correct
6	Correct	14 ms	6876 KB	Output is correct
7	Correct	13 ms	6872 KB	Output is correct
8	Correct	15 ms	7088 KB	Output is correct
9	Correct	19 ms	7260 KB	Output is correct
10	Correct	19 ms	7260 KB	Output is correct
11	Correct	14 ms	7000 KB	Output is correct
12	Correct	36 ms	9044 KB	Output is correct
13	Correct	39 ms	12372 KB	Output is correct
14	Correct	63 ms	14932 KB	Output is correct
15	Correct	65 ms	15184 KB	Output is correct
16	Correct	88 ms	18320 KB	Output is correct
17	Correct	103 ms	23376 KB	Output is correct
18	Correct	103 ms	22392 KB	Output is correct
19	Correct	113 ms	23376 KB	Output is correct
20	Correct	104 ms	23376 KB	Output is correct