Submission #450371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450371	2021-08-02T16:04:45 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	1000 ms	39572 KB

jobs

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
typedef vector<pi> vpi;
typedef map<ll, ll> mape;

#define rep(i, a, b) for(ll i=(ll)a;i<=(ll)b;i++)
#define per(i, a, b) for(ll i=(ll)a;i>=(ll)b;i--)
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
#define pb push_back
#define mkp make_pair
#define all(v) v.begin(), v.end()
#define gap ' '
#define ff first
#define ss second
#define pie acos(-1.0)

const ll maxn = 1e5 + 10;
const ll INF = 1e9 + 10;
const double prec = 1e-8;

vector< vi > adj(maxn, vi());

void solve()
{
    ll days, delay, n;
    cin >> days >> delay >> n;
    vi v(n);
    rep(i, 0, n-1) cin >> v[i];
    vpi clone;
    rep(i, 0, n-1) clone.pb(mkp(v[i], i + 1));
    sort(all(clone));
    ll l = 1, r = n;
    priority_queue< ll, vi, greater<ll> > st;
    while(l < r) {
        ll mid = (l + r) / 2;
        rep(i, 0, mid - 1) st.push(clone[i].ff);
        bool ok = true;
        rep(i, mid, n - 1) {
            ll x = st.top();
            st.pop();
            if(x + 1 > clone[i].ff + delay) {
                ok = false;
                break;
            }
            else st.push(max(x + 1, clone[i].ff));
        }
        if(ok) r = mid;
        else l = mid + 1;
        while(!st.empty()) st.pop();
    }
    cout << r << endl;
    rep(i, 0, r-1) {
        st.push(clone[i].ff);
        adj[clone[i].ff].pb(clone[i].ss);
    }
    rep(i, r, n-1) {
        ll x = st.top();
        st.pop();
        ll mx = max(x + 1, clone[i].ff);
        adj[mx].pb(clone[i].ss);
        st.push(mx);
    }
    while(!st.empty()) st.pop();
    rep(i, 1, days) {
        for(auto y : adj[i]) cout << y << ' ';
        cout << 0 << endl;
    }
}

int main()
{
    fastio;

    //freopen("angry.in", "r", stdin);
    //freopen("angry.out", "w", stdout);

    ll T = 1;
    //cin >> T;
    while(T--) solve();

    return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	7204 KB	Output is correct
2	Correct	108 ms	7404 KB	Output is correct
3	Correct	112 ms	7224 KB	Output is correct
4	Correct	109 ms	7204 KB	Output is correct
5	Correct	106 ms	7228 KB	Output is correct
6	Correct	109 ms	7332 KB	Output is correct
7	Correct	109 ms	7228 KB	Output is correct
8	Correct	109 ms	7320 KB	Output is correct
9	Correct	260 ms	7196 KB	Output is correct
10	Correct	267 ms	7388 KB	Output is correct
11	Correct	106 ms	6936 KB	Output is correct
12	Correct	216 ms	11456 KB	Output is correct
13	Correct	331 ms	16812 KB	Output is correct
14	Correct	495 ms	21448 KB	Output is correct
15	Correct	567 ms	23792 KB	Output is correct
16	Correct	736 ms	28432 KB	Output is correct
17	Runtime error	865 ms	36648 KB	Memory limit exceeded
18	Runtime error	985 ms	38164 KB	Memory limit exceeded
19	Execution timed out	1095 ms	39572 KB	Time limit exceeded
20	Runtime error	875 ms	36736 KB	Memory limit exceeded