Submission #492937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492937	2021-12-09T19:42:19 Z	_swet	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	386 ms	21016 KB

jobs

#ifdef _BELUGA 
#include "DEBUG.h"
#else
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
using namespace std;
#define debug(...) 
#endif

#define int long long
// #define endl '\n'
#define sz(a) (int)((a).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
#define uniq(a) (a).erase(unique(all(a)),(a).end())
#define sum(a) accumulate(all(a), 0ll)
#define rotl(x, a) rotate(x.begin(), x.begin()+(a%sz(x)), x.end())
#define rotr(x, a) rotate(x.begin(), x.begin()+sz(x)-(a%sz(x)), x.end())
#define ppc(x) __builtin_popcountll(x) 
#define type(x) remove_reference<decltype(x)>::type

typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef map<int, int> mii;
typedef pair<int, int> pii;

const double pi = 3.141592653589793;

void google() { static int _gtest_ = 1; cout << "Case #" << _gtest_++ << ": "; }

mt19937 rngi(chrono::steady_clock::now().time_since_epoch().count());
int rng() { return uniform_int_distribution<int>(1, numeric_limits<int>::max())(rngi); }

template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& a) { return in >> a.first >> a.second; }
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> a) { return out << a.first << " " << a.second; }
template<typename T>istream& operator>>(istream& in, vector<T>& a) { for (auto& e : a) in >> e ; return in; }
template<typename T>void print(T t) { cout << t; }
template<typename T, typename... Args>void print(T t, Args... args) { cout << t << " "; print(args...); }
template<typename... Args>void printl(Args... args) { print(args...); cout << endl; }

signed main()
{
    int test = 1;
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << setprecision(3) << fixed;

    // cin >> test;    
    // void calc(); calc();
    void code(); while (test--) code();
}

const int mod = 998244353 ^ 1755654; // Confirm It.
const int maxn = 2e5 + 10; // This as well.

void code()
{
    int n,d,m;
    cin>>n>>d>>m;

    vector<pii> vp;
    int h;
    for (int i = 0; i < m; ++i)
    {
        cin>>h;
        vp.push_back({h, i+1});
    }
    sort(all(vp));
    debug(vp);

    auto check = [&](int k)
    {
        int jj=0;
        int cc=0;
        for (int i = 1; i <= n; ++i)
        {
            cc=0;
            while(jj<m && vp[jj].first <= i && cc<k)
            {
                if (vp[jj].first+d < i) return 0;
                cc++;
                jj++;
            }
            debug(jj);
        }
        // if (jj<m) return 0;
        debug(k);
        return 1;
    };

    int l=1, r=m;

    while(l<r)
    {
        int mid = (l+r)/2;

        if (check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printl(l);

    reverse(all(vp));

    for (int i = 0; i < n; ++i)
    {
        h=l;
        while(h && sz(vp) && vp.back().first<=(i+1))
            print(vp.back().second, ""), vp.pop_back(),h--; 
        printl(0);
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2616 KB	Output is correct
2	Correct	41 ms	2544 KB	Output is correct
3	Correct	39 ms	2568 KB	Output is correct
4	Correct	31 ms	2620 KB	Output is correct
5	Correct	32 ms	2620 KB	Output is correct
6	Correct	32 ms	2536 KB	Output is correct
7	Correct	30 ms	2632 KB	Output is correct
8	Correct	32 ms	2628 KB	Output is correct
9	Correct	145 ms	2748 KB	Output is correct
10	Correct	145 ms	2728 KB	Output is correct
11	Correct	34 ms	2508 KB	Output is correct
12	Correct	64 ms	4796 KB	Output is correct
13	Correct	110 ms	8640 KB	Output is correct
14	Correct	136 ms	9492 KB	Output is correct
15	Correct	152 ms	11660 KB	Output is correct
16	Correct	184 ms	16780 KB	Output is correct
17	Correct	220 ms	16764 KB	Output is correct
18	Correct	244 ms	18492 KB	Output is correct
19	Correct	386 ms	21016 KB	Output is correct
20	Correct	228 ms	16812 KB	Output is correct