oj.uz

Submission #239265

# Submission time Handle Problem Language Result Execution time Memory
239265 2020-06-15T04:59:07 Z ant101 Job Scheduling (CEOI12_jobs) C++14
5 / 100
 393 ms 56548 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[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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 27120 KB Output isn't correct
2 Incorrect 44 ms 27256 KB Output isn't correct
3 Incorrect 43 ms 27248 KB Output isn't correct
4 Incorrect 42 ms 27248 KB Output isn't correct
5 Incorrect 44 ms 27248 KB Output isn't correct
6 Incorrect 43 ms 27248 KB Output isn't correct
7 Incorrect 42 ms 27256 KB Output isn't correct
8 Incorrect 43 ms 27384 KB Output isn't correct
9 Incorrect 56 ms 27756 KB Output isn't correct
10 Incorrect 58 ms 27760 KB Output isn't correct
11 Correct 44 ms 27628 KB Output is correct
12 Incorrect 73 ms 31208 KB Output isn't correct
13 Runtime error 101 ms 36196 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 161 ms 39884 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 161 ms 43104 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 274 ms 48100 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 318 ms 53096 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 319 ms 53856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 393 ms 56548 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 312 ms 53204 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)