Submission #528693

#	Time	Username	Problem	Language	Result	Execution time	Memory
528693		Aanjaney	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	433 ms	53476 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MODA 998244353
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sorta(A, N) sort(A, A + N)
#define debug(x) cerr << #x << " is " << x;
#define rep(i, a, N) for (ll i = a; i < N; i++)
#define f first
#define s second
#define uniq(v)                                       \
    {                                                 \
        sort(v.begin(), v.end());                     \
        v.erase(unique(v.begin(), v.end()), v.end()); \
    }
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
pair<bool, vector<vector<ll> > > check(const vector<pair<ll, ll> > &a, ll machines, ll N, ll D)
{

    vector<vector<ll> > sched(N);
    ll pos = 0, flag = 1, M = a.size();
    rep(day, 1, N + 1)
    {
        rep(machine, 0, machines)
        {
            if (a[pos].f > day)
                break;
            if (a[pos].f + D >= day)
                sched[day - 1].pb(a[pos++].s);
            else
            {
                return make_pair(false, sched);
            }
            if (pos == M)
                return make_pair(true, sched);
        }
    }
    return make_pair(false, sched);
}
void solve(ll tcase)
{
    ll N, D, M;
    cin >> N >> D >> M;
    vector<pair<ll, ll> > a(M);
    rep(i, 0, M)
    {
        cin >> a[i].f;
        a[i].s = i;
    }
    sortv(a);
    ll lo = 1, hi = M + 1;
    pair<bool, vector<vector<ll> > > p;
    while (lo < hi)
    {
        ll mid = (lo + hi) / 2;
        p = check(a, mid, N, D);
        if (p.f)
            hi = mid;
        else
            lo = mid + 1;
    }
    cout << hi << "\n";
    p = check(a, hi, N, D);
    rep(i, 0, N)
    {
        for (auto j : p.s[i])
            cout << j + 1 << ' ';
        cout << "0\n";
    }
}
int main()
{

    speed;
    ll t = 1;
    rep(i, 1, t + 1)
        solve(i);
}

Compilation message (stderr)

jobs.cpp: In function 'std::pair<bool, std::vector<std::vector<long long int> > > check(const std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
jobs.cpp:27:17: warning: unused variable 'flag' [-Wunused-variable]
   27 |     ll pos = 0, flag = 1, M = a.size();
      |                 ^~~~

• Subtask 1: 75 / 100