oj.uz

Submission #116012

# Submission time Handle Problem Language Result Execution time Memory
116012 2019-06-10T07:41:22 Z evpipis Job Scheduling (CEOI12_jobs) C++11
0 / 100
 563 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int len = 1e6+5;
int n, d, m, st[len];
vector<int> out[len], day[len];
queue<int> myq;

bool check(int k){
    while (!myq.empty())
        myq.pop();

    for (int i = 1; i <= n; i++){
        out[i].clear();

        for (int j = 0; j < day[i].size(); j++)
            myq.push(day[i][j]);

        int rem = k;
        while (rem-- && !myq.empty()){
            int cur = myq.front();
            myq.pop();

            //printf("cur = %d, val = %d\n", cur, st[cur]);

            if (i > st[cur]+d)
                return false;

            out[i].pb(cur);
        }
    }

    return (myq.empty());
}

int bs(){
    int l = 0, r = m, ans = 0;
    while (l <= r){
        int mid = (l+r)/2;
        //printf("l = %d, r = %d, mid = %d\n", l, r, mid);

        if (check(mid))
            r = mid-1, ans = mid;
        else
            l = mid+1;
    }

    return ans;
}

int main(){
    scanf("%d %d %d", &n, &d, &m);
    for (int i = 1; i <= m; i++){
        scanf("%d", &st[i]);
        day[st[i]].pb(i);
        //printf("i = %d, st = %d\n", i, st[i]);
    }

    int ans = bs();
    check(ans);

    printf("%d\n", ans);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < out[i].size(); j++)
            printf("%d ", out[i][j]);
        printf("0\n");
    }
    return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:17:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < day[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < out[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~
jobs.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &d, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &st[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 49776 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 68 ms 49836 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 66 ms 49776 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 66 ms 49776 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 66 ms 49788 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 66 ms 49904 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 66 ms 50048 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 67 ms 50028 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 72 ms 49656 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 74 ms 49788 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
11 Runtime error 76 ms 49656 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
12 Runtime error 109 ms 51796 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
13 Runtime error 147 ms 54920 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 299 ms 58224 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 247 ms 58568 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 384 ms 61676 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 466 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 461 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 563 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 469 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)