oj.uz

Submission #224423

# Submission time Handle Problem Language Result Execution time Memory
224423 2020-04-17T20:41:04 Z MKopchev Job Scheduling (CEOI12_jobs) C++14
100 / 100
 357 ms 17144 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX=1e6+42;

int n,d,m;

pair<int,int> inp[MX];

bool can(int sz)
{
    int pos=1;

    for(int day=1;day<=n&&pos<=m;day++)
    {
        if(inp[pos].first+d<day)return 0;

        int pos_help=pos;

        while(pos_help<=m&&pos_help-pos<sz&&inp[pos_help].first<=day)
        {
            pos_help++;
        }

        pos=pos_help;
    }

    return pos>m;
}
int main()
{
    scanf("%i%i%i",&n,&d,&m);

    for(int i=1;i<=m;i++)
    {
        scanf("%i",&inp[i].first);
        inp[i].second=i;
    }

    sort(inp+1,inp+m+1);

    int ok=m,not_ok=0;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        if(can(av))ok=av;
        else not_ok=av;
    }

    printf("%i\n",ok);

    int pos=1;

    for(int day=1;day<=n;day++)
    {
        int pos_help=pos;

        while(pos_help<=m&&pos_help-pos<ok&&inp[pos_help].first<=day)
        {
            printf("%i ",inp[pos_help].second);
            pos_help++;
        }

        pos=pos_help;

        printf("0\n");
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&d,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2040 KB Output is correct
2 Correct 29 ms 2040 KB Output is correct
3 Correct 30 ms 2040 KB Output is correct
4 Correct 29 ms 2040 KB Output is correct
5 Correct 28 ms 2040 KB Output is correct
6 Correct 30 ms 2040 KB Output is correct
7 Correct 29 ms 2048 KB Output is correct
8 Correct 29 ms 1980 KB Output is correct
9 Correct 44 ms 2168 KB Output is correct
10 Correct 43 ms 2296 KB Output is correct
11 Correct 40 ms 2172 KB Output is correct
12 Correct 86 ms 3960 KB Output is correct
13 Correct 116 ms 5884 KB Output is correct
14 Correct 157 ms 8184 KB Output is correct
15 Correct 185 ms 9592 KB Output is correct
16 Correct 229 ms 12028 KB Output is correct
17 Correct 266 ms 13944 KB Output is correct
18 Correct 300 ms 15320 KB Output is correct
19 Correct 357 ms 17144 KB Output is correct
20 Correct 272 ms 13944 KB Output is correct