Submission #450367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450367	2021-08-02T16:01:43 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1000 ms	40264 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 = 0, 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	108 ms	7284 KB	Output is correct
2	Correct	109 ms	7324 KB	Output is correct
3	Correct	108 ms	7320 KB	Output is correct
4	Correct	116 ms	7212 KB	Output is correct
5	Correct	107 ms	7328 KB	Output is correct
6	Correct	110 ms	7252 KB	Output is correct
7	Correct	113 ms	7340 KB	Output is correct
8	Correct	108 ms	7328 KB	Output is correct
9	Correct	261 ms	7204 KB	Output is correct
10	Correct	265 ms	7324 KB	Output is correct
11	Correct	102 ms	6948 KB	Output is correct
12	Correct	219 ms	11440 KB	Output is correct
13	Correct	326 ms	17072 KB	Output is correct
14	Correct	497 ms	21520 KB	Output is correct
15	Correct	552 ms	23852 KB	Output is correct
16	Correct	747 ms	28352 KB	Output is correct
17	Runtime error	885 ms	36580 KB	Memory limit exceeded
18	Execution timed out	1046 ms	38300 KB	Time limit exceeded
19	Execution timed out	1091 ms	40264 KB	Time limit exceeded
20	Runtime error	889 ms	36636 KB	Memory limit exceeded