oj.uz

Submission #239271

# Submission time Handle Problem Language Result Execution time Memory
239271 2020-06-15T05:31:48 Z ant101 Job Scheduling (CEOI12_jobs) C++14
80 / 100
 689 ms 39220 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 1000010;

ll jobs[MAXN];
ll N, M, D;
vector<ll> buckets[100010];
vector<ll> ans[100010];

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
//    ifstream fin;
//    fin.open("in.10");
    cin >> N >> D >> M;
    for (ll i = 0; i<M; i++) {
        cin >> jobs[i];
        buckets[jobs[i]].push_back(i);
    }
    ll L = 1, R = M;
    while (L <= R) {
        for (ll i = 0; i<100010; i++) {
            ans[i].clear();
        }
        ll mid = (L+R)/2;
        queue<ll> q;
        ll bad = false;
        for (ll i = 1; i<=N; i++) {
            for (ll j = 0; j<buckets[i].size(); j++) {
                q.push(buckets[i][j]);
            }
            for (ll j = 0; j<mid; j++) {
                if (q.empty()) {
                    break;
                }
                if (i-jobs[q.front()] > D) {
                    bad = true;
                    break;
                }
                ans[i].push_back(q.front());
                q.pop();
            }
            if (bad) {
                break;
            }
        }
        if (L == R) {
            break;
        }
        if (bad) {
            L = mid+1;
        } else {
            R = mid;
        }
    }
//    vector<ll> list;
//    for (ll i = 1; i<=N; i++) {
//        for (ll j = 0; j<buckets[i].size(); j++) {
//            list.push_back(buckets[i][j]);
//        }
//    }
//    cout << L << "\n";
//    ll cnt = 0;
//    for (ll i = 0; i<list.size(); i++) {
//        if (i != 0 && i%L == 0) {
//            cout << 0 << "\n";
//            cnt++;
//        }
//        cout << 1+list[i] << " ";
//    }
//    cout << "0\n";
    cout << L << "\n";
    for (ll i = 1; i<=N; i++) {
        for (ll j = 0; j<ans[i].size(); j++) {
            cout << ans[i][j]+1 << " ";
        }
        cout << "0\n";
    }
    
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:87:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (ll j = 0; j<buckets[i].size(); j++) {
                            ~^~~~~~~~~~~~~~~~~~
jobs.cpp:132:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j<ans[i].size(); j++) {
                        ~^~~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9712 KB Output is correct
2 Correct 41 ms 9712 KB Output is correct
3 Correct 43 ms 9708 KB Output is correct
4 Correct 45 ms 9712 KB Output is correct
5 Correct 40 ms 9708 KB Output is correct
6 Correct 40 ms 9712 KB Output is correct
7 Correct 42 ms 9712 KB Output is correct
8 Correct 41 ms 9712 KB Output is correct
9 Correct 49 ms 9080 KB Output is correct
10 Correct 47 ms 9080 KB Output is correct
11 Correct 46 ms 8952 KB Output is correct
12 Correct 93 ms 12792 KB Output is correct
13 Correct 151 ms 19064 KB Output is correct
14 Correct 222 ms 23132 KB Output is correct
15 Correct 228 ms 25464 KB Output is correct
16 Correct 342 ms 31352 KB Output is correct
17 Runtime error 485 ms 39220 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 523 ms 36788 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 689 ms 38904 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 461 ms 39160 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)