Submission #49188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49188	2018-05-23T13:10:26 Z	Benq	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	454 ms	20172 KB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

vi todo[MX], ans[MX];
int N, D, M;

int gen(int x, bool b = 0) {
    // return 0;
    queue<pi> cur;
    int mx = 0;
    FOR(i,1,N+1) {
        for (int j: todo[i]) cur.push({j,i});
        for (int j = 0; j < x && sz(cur) > 0; ++j) {
            if (b) ans[i].pb(cur.front().f); 
            mx = max(mx,i-cur.front().s);
            cur.pop();
        }
    }
    if (sz(cur)) return MOD;
    return mx;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> D >> M;
    FOR(i,1,M+1) {
        int x; cin >> x;
        todo[x].pb(i);
    }
    int lo = 1, hi = 1000000;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (gen(mid) <= D) hi = mid;
        else lo = mid+1;
    }
    gen(lo,1);
    cout << lo << "\n";
    FOR(i,1,N+1) {
        for (int j: ans[i]) cout << j << " ";
        cout << "0\n";
    }
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	7308 KB	Output is correct
2	Correct	43 ms	7360 KB	Output is correct
3	Correct	75 ms	7404 KB	Output is correct
4	Correct	50 ms	7452 KB	Output is correct
5	Correct	48 ms	7512 KB	Output is correct
6	Correct	48 ms	7556 KB	Output is correct
7	Correct	43 ms	7556 KB	Output is correct
8	Correct	45 ms	7616 KB	Output is correct
9	Correct	58 ms	7616 KB	Output is correct
10	Correct	116 ms	7616 KB	Output is correct
11	Correct	47 ms	7616 KB	Output is correct
12	Correct	98 ms	8688 KB	Output is correct
13	Correct	122 ms	11444 KB	Output is correct
14	Correct	209 ms	14012 KB	Output is correct
15	Correct	197 ms	14012 KB	Output is correct
16	Correct	454 ms	15960 KB	Output is correct
17	Correct	437 ms	20172 KB	Output is correct
18	Correct	329 ms	20172 KB	Output is correct
19	Correct	386 ms	20172 KB	Output is correct
20	Correct	417 ms	20172 KB	Output is correct