oj.uz

Submission #920262

# Submission time Handle Problem Language Result Execution time Memory
920262 2024-02-02T11:13:17 Z Kavelmydex Job Scheduling (CEOI12_jobs) C++17
100 / 100
 181 ms 32184 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define pb push_back
#define f first
#define s second
#define endl "\n"
#define sp ' '
// #define sz size()
#define all(x) (x).begin(),(x).end()

const int N = 1e5+10, OO = 1e18, mod = 1e9+7;
void tr(int a, int b){cout << a << sp << b << endl;}
vi a[N], ans[N], cur[N];

int32_t main() {            
    ios::sync_with_stdio(0); cin.tie(0);
    int n,d,m; cin >> n >> d >> m;
    For(i,m){
        int x; cin >> x;
        a[x].pb(i+1);
    }
    int l=0, r = 1e7;
    while(r > l+1){
        int mid = (l+r)/2, ok = 1;
        deque <pi> v;
        rep(i,1,n+1) cur[i].clear();
        rep(i,1,n+1){
            int sz = v.size();
            For(j, min(mid, sz)){
                if(i-v.front().s > d) ok = 0;
                cur[i].pb(v.front().f);
                v.pop_front();   
            }
            int c = a[i].size(), ava = mid - min(mid,sz);
            for(int j=0; j < c; ++j){
                if(j < ava) cur[i].pb(a[i][j]);
                else v.pb({a[i][j],i});
            }   
        }
        if(ok){ 
            r = mid;
            rep(i,1,n+1) ans[i] = cur[i];
        }
        else l = mid;
    }
    cout << r << endl;
    rep(i,1,n+1){
        for(int j: ans[i]) cout << j << sp;
        cout << 0 << endl;
    }
    return 0;   
}

Compilation message

jobs.cpp:16:28: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int N = 1e5+10, OO = 1e18, mod = 1e9+7;
      |                            ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10600 KB Output is correct
2 Correct 20 ms 10564 KB Output is correct
3 Correct 19 ms 10564 KB Output is correct
4 Correct 21 ms 10680 KB Output is correct
5 Correct 20 ms 10712 KB Output is correct
6 Correct 19 ms 10568 KB Output is correct
7 Correct 21 ms 10508 KB Output is correct
8 Correct 20 ms 10572 KB Output is correct
9 Correct 33 ms 10320 KB Output is correct
10 Correct 34 ms 10528 KB Output is correct
11 Correct 19 ms 10064 KB Output is correct
12 Correct 39 ms 12624 KB Output is correct
13 Correct 63 ms 16408 KB Output is correct
14 Correct 86 ms 19692 KB Output is correct
15 Correct 86 ms 21532 KB Output is correct
16 Correct 120 ms 25144 KB Output is correct
17 Correct 166 ms 29684 KB Output is correct
18 Correct 145 ms 29580 KB Output is correct
19 Correct 181 ms 32184 KB Output is correct
20 Correct 158 ms 29680 KB Output is correct