Submission #565602

#	Time	Username	Problem	Language	Result	Execution time	Memory
565602		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	368 ms	24020 KiB

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;
        }
        // if (day > n)
        //     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 / 100