oj.uz

Submission #116011

# Submission time Handle Problem Language Result Execution time Memory
116011 2019-06-10T07:36:41 Z evpipis Job Scheduling (CEOI12_jobs) C++17
0 / 100
 529 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 68 ms 50032 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 69 ms 50032 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 69 ms 50028 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 68 ms 50032 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 67 ms 50000 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 68 ms 50004 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 69 ms 50000 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 68 ms 50032 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 75 ms 49784 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 76 ms 49812 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
11 Runtime error 75 ms 49812 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
12 Runtime error 118 ms 52324 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
13 Runtime error 157 ms 55732 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 261 ms 59956 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 240 ms 60280 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 424 ms 64120 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 439 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 484 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 529 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)