Submission #116070

#	Time	Username	Problem	Language	Result	Execution time	Memory
116070		evpipis	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	530 ms	26724 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int len1 = 1e6+5, len2 = 1e5+5;
int n, d, m, st[len1];
vector<int> out[len2], day[len2];
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 (!myq.empty() && rem){
            int cur = myq.front();
            myq.pop();
            rem--;

            //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 = 1, 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 (stderr)

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:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < out[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~
jobs.cpp:54: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:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &st[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100