Submission #726860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
726860	2023-04-19T13:04:58 Z	hariaakas646	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	306 ms	23316 KB

jobs

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

#define scd(t) scanf("%d", &t)
#define scld(t) scanf("%ld", &t)
#define sclld(t) scanf("%lld", &t)
#define scc(t) scanf("%c", &t)
#define scs(t) scanf("%s", t)
#define scf(t) scanf("%f", &t)
#define sclf(t) scanf("%lf", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define MP make_pair
#define pb push_back
#define f first
#define s second
typedef long int li;
typedef unsigned long int uli;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;

vvi vec;
int n, d, m;

bool check(int x)
{
    queue<int> q;
    forr(i, 1, n + 1)
    {
        for (auto e : vec[i])
            q.push(i);
        int curr = x;
        while (curr && q.size())
        {
            int p = q.front();
            q.pop();
            if (i - p > d)
                return false;
            curr--;
        }
    }
    return true;
}

int main()
{

    scd(n);
    scd(d);
    scd(m);
    vec = vvi(n + 1);
    forr(i, 1, m + 1)
    {
        int a;
        scd(a);
        vec[a].pb(i);
    }
    int hi = m;
    int lo = 1;

    while (hi != lo)
    {
        int mid = (hi + lo) / 2;
        if (check(mid))
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    queue<pii> q;
    vvi out(n + 1);
    forr(i, 1, n + 1)
    {
        for (auto e : vec[i])
            q.push({i, e});
        int curr = lo;
        while (curr && q.size())
        {
            pii p = q.front();
            q.pop();
            out[i].pb(p.s);
            curr--;
        }
    }
    printf("%d\n", lo);
    forr(i, 1, n + 1)
    {
        for (auto e : out[i])
        {
            printf("%d ", e);
        }
        printf("0\n");
    }
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:43:19: warning: unused variable 'e' [-Wunused-variable]
   43 |         for (auto e : vec[i])
      |                   ^
jobs.cpp: In function 'int main()':
jobs.cpp:6:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
jobs.cpp:61:5: note: in expansion of macro 'scd'
   61 |     scd(n);
      |     ^~~
jobs.cpp:6:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
jobs.cpp:62:5: note: in expansion of macro 'scd'
   62 |     scd(d);
      |     ^~~
jobs.cpp:6:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
jobs.cpp:63:5: note: in expansion of macro 'scd'
   63 |     scd(m);
      |     ^~~
jobs.cpp:6:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
jobs.cpp:68:9: note: in expansion of macro 'scd'
   68 |         scd(a);
      |         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	3268 KB	Output is correct
2	Correct	30 ms	3308 KB	Output is correct
3	Correct	29 ms	3268 KB	Output is correct
4	Correct	29 ms	3244 KB	Output is correct
5	Correct	30 ms	3228 KB	Output is correct
6	Correct	33 ms	3328 KB	Output is correct
7	Correct	30 ms	3308 KB	Output is correct
8	Correct	30 ms	3356 KB	Output is correct
9	Correct	38 ms	7120 KB	Output is correct
10	Correct	38 ms	7100 KB	Output is correct
11	Correct	30 ms	2296 KB	Output is correct
12	Correct	76 ms	4432 KB	Output is correct
13	Correct	121 ms	7676 KB	Output is correct
14	Correct	154 ms	10800 KB	Output is correct
15	Correct	160 ms	10344 KB	Output is correct
16	Correct	222 ms	13900 KB	Output is correct
17	Correct	263 ms	19040 KB	Output is correct
18	Correct	260 ms	17612 KB	Output is correct
19	Correct	306 ms	23316 KB	Output is correct
20	Correct	264 ms	18928 KB	Output is correct