oj.uz

Submission #920229

# Submission time Handle Problem Language Result Execution time Memory
920229 2024-02-02T10:01:41 Z Kavelmydex Job Scheduling (CEOI12_jobs) C++17
75 / 100
 226 ms 46752 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;   
}

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 13392 KB Output is correct
2 Correct 23 ms 13172 KB Output is correct
3 Correct 21 ms 13400 KB Output is correct
4 Correct 26 ms 13400 KB Output is correct
5 Correct 22 ms 13396 KB Output is correct
6 Correct 21 ms 13400 KB Output is correct
7 Correct 21 ms 13400 KB Output is correct
8 Correct 21 ms 13388 KB Output is correct
9 Correct 35 ms 12316 KB Output is correct
10 Correct 39 ms 12312 KB Output is correct
11 Correct 21 ms 11600 KB Output is correct
12 Correct 38 ms 15440 KB Output is correct
13 Correct 58 ms 21424 KB Output is correct
14 Correct 99 ms 26380 KB Output is correct
15 Correct 92 ms 29444 KB Output is correct
16 Runtime error 166 ms 34040 KB Memory limit exceeded
17 Runtime error 226 ms 42812 KB Memory limit exceeded
18 Runtime error 219 ms 43000 KB Memory limit exceeded
19 Runtime error 222 ms 46752 KB Memory limit exceeded
20 Runtime error 205 ms 42956 KB Memory limit exceeded