Submission #565652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
565652	2022-05-21T08:13:33 Z	PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	325 ms	23752 KB

jobs

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

#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define ff first
#define ss second
#define endl "\n"
#define pb(x) push_back(x)
#define pp() pop_back()
#define inf MAX_INT
#define dvg(x) cout << #x << " " << x << endl;
#define dvg2(x, y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define dvgv(x)           \
    cout << #x << " { ";  \
    for (auto i : x)      \
    {                     \
        cout << i << " "; \
    }                     \
    cout << "}" << endl;
#define dvgp(x) cout << #x " {" << x.ff << ", " << x.ss << "}" << endl;
int dx[]{-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int const N = 1e5 + 10;
vpii v;
vvi ans;
int n, d, m;

bool ok(int x)
{
    int day = 1, machines = 1;
    ans = vvi(n + 1, vi());
    for (int i = 0; i < m; i++)
    {
        while (day < v[i].ff)
        {
            day++;
            machines = 1;
        }
        if (day - v[i].ff > d)
        {
            return 0;
        }

        ans[day].pb(v[i].ss);
        machines++;
        if (machines > x)
        {
            day++;
            machines = 1;
        }
    }
    return 1;
}
int main()
{
    fastio();

    cin >> n >> d >> m;
    v = vpii(m);
    for (int i = 0; i < m; i++)
    {
        cin >> v[i].ff;
        v[i].ss = i + 1;
    }
    sort(v.begin(), v.end());
    int lo = 0, hi = 1e5 + 12;
    while (lo + 1 < hi)
    {
        int mid = (hi + lo) / 2;
        if (ok(mid))
            hi = mid;
        else
            lo = mid;
    }
    cout << hi << endl;
    ok(hi);
    for (int i = 1; i <= n; i++)
    {
        for (auto j : ans[i])
            cout << j << " ";
        cout << 0 << endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2648 KB	Output is correct
2	Correct	28 ms	2716 KB	Output is correct
3	Correct	29 ms	2728 KB	Output is correct
4	Correct	28 ms	2612 KB	Output is correct
5	Correct	27 ms	2656 KB	Output is correct
6	Correct	28 ms	2636 KB	Output is correct
7	Correct	27 ms	2656 KB	Output is correct
8	Correct	30 ms	2720 KB	Output is correct
9	Correct	56 ms	8664 KB	Output is correct
10	Correct	54 ms	9452 KB	Output is correct
11	Correct	40 ms	2192 KB	Output is correct
12	Correct	74 ms	4240 KB	Output is correct
13	Correct	105 ms	6640 KB	Output is correct
14	Correct	165 ms	9288 KB	Output is correct
15	Correct	173 ms	9672 KB	Output is correct
16	Correct	253 ms	12252 KB	Output is correct
17	Correct	274 ms	15832 KB	Output is correct
18	Correct	274 ms	16588 KB	Output is correct
19	Correct	325 ms	23752 KB	Output is correct
20	Correct	282 ms	15832 KB	Output is correct