Submission #1275204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275204		tredsused70	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	169 ms	14652 KiB

jobs

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 100011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

bool check(vector<int> vc, int d, int ans) {
    int cur = 1;
    int n = vc.size();
    for(int i = 1; i < n; i++) {
        int cnt = ans;
        while(cnt > 0 && cur <= i) {
            int t = min(cnt, vc[cur]);
            cnt -= t;
            vc[cur] -= t;
            if(vc[cur] == 0)
                cur++;
        }
        if(i - d >= cur)
            return 0;
    }
    return 1;
}

void solve()
{
    int n, m, d;
    cin >> n >> d >> m;
    vector<pair<int, int>> vc(m);
    vector<int> cnt(n + 1, 0);
    for(int i = 0; i < m; i++) {
        int a;
        cin >> a;
        vc[i] = mpr(a, i + 1);
        cnt[a]++;
    }
    sort(all(vc));
    int l = 0, r = m;
    while(l + 1 < r) {
        int md = (l + r) / 2;
        if(check(cnt, d, md))
            r = md;
        else
            l = md;
    }
    int ans = r;
    cout << ans << "\n";
    int cur = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < ans; j++) {
            if(cur == m)
                break;
            cout << vc[cur].second << " ";
            cur++;
        }
        cout << "0\n";
    }
    return ;
}

int main()
{
    //freopen("cruise.in","r",stdin);
    //freopen("cruise.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    return 0;
}

/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3

5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
*/

• Subtask 1: 100 / 100