oj.uz

Submission #745505

# Submission time Handle Problem Language Result Execution time Memory
745505 2023-05-20T08:57:50 Z Nafeeszx Job Scheduling (CEOI12_jobs) C++14
100 / 100
 143 ms 23756 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;

const int mod = 1e9 + 7, MOD = 998244353;

const int N = 2005;

int main() 
{	
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, d;
    cin >> n >> d >> m;
    vector<int> v(m);
    vector<vector<int>> tind(n-d+1);
    F0R(i, m) {
        cin >> v[i];
        tind[v[i]].push_back(i);
    }
    int hi = m, lo = 0;
    while(hi - lo > 1) {
        int mid = (hi+lo)/2;
        bool ok = true;
        int c = 0;
        FOR(i, 1, n-d) {
            if(c + (int)tind[i].size() > mid * (d+1)) {
                ok = false;
                break;
            }
            c = max(0, c+(int)tind[i].size()-mid);
        }
        //cout << mid << '\n';
        if(ok) hi=mid;
        else lo=mid;
    }
    cout << hi << '\n';

    int day = 1;
    int mach = 0;
    vector<vector<int>> res(n+1);
    FOR(i, 1, n-d) {
        trav(u, tind[i]) {
            res[day].push_back(u);
            mach++;
            if(mach%hi==0) {
                mach = 0; day++;
            }
        }
        if(day==i) {
            day++;
            mach=0;
        }
    }
    FOR(i, 1, n) {
        trav(v, res[i]) cout << v+1 << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3028 KB Output is correct
2 Correct 16 ms 3156 KB Output is correct
3 Correct 15 ms 3152 KB Output is correct
4 Correct 15 ms 3028 KB Output is correct
5 Correct 15 ms 3028 KB Output is correct
6 Correct 14 ms 3028 KB Output is correct
7 Correct 15 ms 3080 KB Output is correct
8 Correct 15 ms 3068 KB Output is correct
9 Correct 21 ms 7500 KB Output is correct
10 Correct 20 ms 7500 KB Output is correct
11 Correct 19 ms 2752 KB Output is correct
12 Correct 36 ms 4808 KB Output is correct
13 Correct 48 ms 8012 KB Output is correct
14 Correct 74 ms 10716 KB Output is correct
15 Correct 81 ms 10872 KB Output is correct
16 Correct 109 ms 13872 KB Output is correct
17 Correct 129 ms 18996 KB Output is correct
18 Correct 136 ms 18328 KB Output is correct
19 Correct 143 ms 23756 KB Output is correct
20 Correct 140 ms 18892 KB Output is correct