Submission #1131036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131036		aly	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	369 ms	26496 KiB

jobs

/*
$$$$$$\              $$\     $$\
$$  __$$\             $$ |    $$ |
$$ /  $$ |$$\   $$\ $$$$$$\   $$$$$$$\   $$$$$$\   $$$$$$\        $$\
$$$$$$$$ |$$ |  $$ |\_$$  _|  $$  __$$\ $$  __$$\ $$  __$$\       \__|
$$  __$$ |$$ |  $$ |  $$ |    $$ |  $$ |$$ /  $$ |$$ |  \__|
$$ |  $$ |$$ |  $$ |  $$ |$$\ $$ |  $$ |$$ |  $$ |$$ |            $$\
$$ |  $$ |$$$$$$  |  $$$$  |$$ |  $$ |$$$$$$  |$$ |            \__|
\__|  \__| \______/    \____/ \__|  \__| \______/ \__|
$$$$$$$\                      $$$$$$$$\ $$\
$$  __$$\                     $$  _____|$$ |
$$ |  $$ | $$$$$$\   $$$$$$$\ $$ |      $$ | $$$$$$\  $$\   $$\
$$ |  $$ |$$  __$$\ $$  _____|$$$$$\    $$ |$$  __$$\ $$\ $$  |
$$ |  $$ |$$ /  $$ |$$ /      $$  __|   $$ |$$$$$$$$ | $$$$  /
$$ |  $$ |$$ |  $$ |$$ |      $$ |      $$ |$$   ____| $$  $$<
$$$$$$$  |$$$$$$  |$$$$$$$\ $$ |      $$ |$$$$$$$\ $$  /$$\
\_______/  \______/  \_______|\__|      \__| \_______|\__/  \__|
*/
#include <bits/stdc++.h>
using namespace std;

// clang-format off
// <----------------------- Macros Start Here ----------------------->

#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define el   '\n'
#define MOD1 1000000007
#define MOD2 998244353
#define INF numeric_limits<ll>::max()

#define forn(i, req) for (int i = 0; i < req; ++i)
#define forsn(i, st, req) for (int i = st; i < req; ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popFront(x) x.erase(x.begin())
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
typedef long long int ll;
// Typedefs Here
typedef long long int ll;
#define vp64 vector<pair<long long, long long>>
#define vp32 vector<pair<int, int>>
#define v32 vector<int>
#define v64 vector<long long>
typedef priority_queue<ll> priQueNorm;
typedef priority_queue<ll, vector<ll>, greater<ll> > priQueVec;

// <----------------------- Macros End Here ----------------------->

// <----------------------- Debug Utils Start Here ----------------------->
// #ifndef ONLINE_JUDGE
// #define debug(x) cerr << #x <<" "; _print(x); cerr << el;
// #else
// #define debug(x)
// #endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
template <class T, class V> void _print(pair<T, V> p);
template <class T> void _print(vector<T> v);
template <class T> void _print(set<T> v);
template <class T, class V> void _print(map<T, V> v);
template <class T> void _print(multiset<T> v);
template <class T, class V> void _print(pair<T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset<T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map<T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }

// Operator overloads
template<typename T1, typename T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
template<typename T>
istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; }
template<typename T1, typename T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second << el); }
template<typename T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }

// <----------------------- Debug Utils End Here ----------------------->

// <----------------------- Predefined Goodies Start Here ----------------------->

ll GCD(ll a, ll b) {if (b > a) {return GCD(b, a);} if (b == 0) {return a;} return GCD(b, a % b);}
ll LCM(ll a, ll b) { return (a / GCD(a, b)) * b; }
ll pwr(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mminvprime(ll a, ll b) {return pwr(a, b - 2, b);}
ll modAdd(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll modMul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll modSub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll modDiv(ll a, ll b, ll m) {a = a % m; b = b % m; return (modMul(a, mminvprime(b, m), m) + m) % m;}
bool isPrime(ll n) { if(n < 2) return false; for(ll k = 2; k * k <= n; k++) if(n % k == 0) return false; return true; }

// <----------------------- Predefined Goodies End Here ----------------------->
pair<int,vector<v32>> firstTrue(int lo, int hi, function<pair<bool, vector<v32>>(int)> f) {
    hi++;
    vector<v32> res;
    while (lo < hi) {
        int md = (lo + hi) / 2;
        auto result = f(md);
        if (result.first) {
            res = result.second;
            hi = md;
        } else {
            lo = md + 1;
        }
    }
    return {lo, res};
}

// clang-format on
int n,d,m;
void solveMyProblem(istream &cin, ostream &cout, ll testCase) {
    cin >> n >> d >> m;
    vp32 jobs(m);

    forn(i, m) {
        int day;
        cin >> day;
        jobs[i] = {day, i + 1};
    }
    sort(all(jobs));

    pair<int, vector<v32>> ans = firstTrue(1, m, [&](int machines) {
        vector<v32> schedule(n);
        int reqnum = 0;

        forsn(day, 1, n + 1) {
            forn(machine, machines) {
                if (jobs[reqnum].first > day) break;
                if (jobs[reqnum].first + d >= day) {
                    schedule[day - 1].pb(jobs[reqnum++].second);
                } else {
                    return make_pair(false, schedule);
                }
                   if (reqnum == m) return make_pair(true, schedule);
            }
         
        }
        return make_pair(false, schedule);
    });
   cout<<ans.ff<<el;
  for (const auto &daySchedule : ans.second) {
        for (int job : daySchedule) cout << job << " ";
        cout << 0 << el;
    }

} 

int32_t main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
//     freopen("error.txt", "w", stderr);
//     clock_t startClock = clock();
// #endif
    FastIO;
    istream &in(cin);
    ostream &out(cout);
    /*
    Start Coding Here
    */

    ll t = 1;
    // cin >> t;
    for (ll test = 1; test <= t; test++) {
        solveMyProblem(in, out, test);
    }

    /*
    Code Ends Here
    */
// #ifndef ONLINE_JUDGE
//     clock_t endClock = clock();
//     double timeTaken = double(endClock - startClock) / double(CLOCKS_PER_SEC);
//     cout << fixed << setprecision(7);
//     cout << "Time Taken: " << timeTaken << " Sec";
// #endif
    return 0;
}

• Subtask 1: 100 / 100