Submission #239265

#	Time	Username	Problem	Language	Result	Execution time	Memory
239265		ant101	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	393 ms	56548 KiB

jobs

#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[MAXN];

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> D >> M;
    for (ll i = 0; i<M; i++) {
        cin >> jobs[i];
        buckets[jobs[i]].push_back(i);
    }
    ll L = 1, R = N;
    while (L < R) {
        ll mid = (L+R)/2;
        queue<ll> q;
        for (ll i = 0; i<buckets[1].size(); i++) {
            q.push(buckets[1][i]);
        }
        ll bad = false;
        for (ll i = 2; i<=N-D; i++) {
            for (ll j = 0; j<mid; j++) {
                if (q.empty()) {
                    break;
                }
                if (i-jobs[q.front()] > D) {
                    bad = true;
                    break;
                }
                q.pop();
            }
            if (bad) {
                break;
            }
            for (ll j = 0; j<buckets[i].size(); j++) {
                q.push(buckets[i][j]);
            }
        }
        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";
    for (ll i = cnt+1; i<N; i++) {
        cout << 0 << "\n";
    }
    
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 100