Submission #1318332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318332		theoneandonlytron	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	315 ms	45472 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
int n,d,m;
vector <pair<ll,ll>> l1;
bool check(ll a, vector <ll> f_table){
    ll answ = 0;
    for (int i =1 ; i <= (n-d); i++){
        if (f_table[i] < a){
            answ -= min(answ, a - f_table[i]);
        }
        else{
            answ += f_table[i] - a;
        }
    }
    if (answ >= 1){
        return false;
    }
    else{
        return true;
    }
}

int main(){
    cin >> n >> d >> m;
    vector <ll> f_table(n+1,0);
    vector <vector <ll>> final(n+1);
    for (int i = 0; i < m; i++){
        ll a;
        cin >> a;
        l1.push_back({a, i+1});
        f_table[a] += 1;
        final[a].push_back(i+1);
    }
    sort(l1.begin(), l1.end());
    ll l = 1;
    ll r = m;
    while (l!=r){
        ll mid_point = (l+r)/2;
        if (check(mid_point, f_table)){
            r = mid_point;
        }
        else{
            l = mid_point + 1;
        }
    }
    vector <ll> counter(n+1, 0);
    queue <ll> idk;
    for (int i = 1; i <= n - d; i++){
        if (final[i].size() > l){
            while (final[i].size() > l){
                ll current = final[i].back();
                final[i].pop_back();
                idk.push(current);
            }
        }
        else{
            while (final[i].size() < l && idk.size() >= 1){
                ll current = idk.front();
                idk.pop();
                final[i].push_back(current);
            }
        }
    }
    cout << l << "\n";
    for (int i = 1; i <= n; i++){
        for (auto &p : final[i]){
            cout << p << " ";
        }
        cout << 0 << "\n";
    }
}

• Subtask 1: 0 / 100