Submission #450363

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450363	2021-08-02T15:45:41 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	65 / 100	1000 ms	45540 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;
    while(l < r) {
        ll mid = (l + r) / 2;
        multiset<ll> st;
        rep(i, 0, mid - 1) st.insert(clone[i].ff);
        bool ok = true;
        rep(i, mid, n - 1) {
            ll x = *st.begin();
            st.erase(st.begin());
            if(x + 1 > clone[i].ff + delay) {
                ok = false;
                break;
            }
            else st.insert(max(x + 1, clone[i].ff));
        }
        if(ok) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    multiset<ll> st;
    rep(i, 0, r-1) {
        st.insert(clone[i].ff);
        adj[clone[i].ff].pb(clone[i].ss);
    }
    rep(i, r, n-1) {
        ll x = *st.begin();
        st.erase(st.begin());
        ll mx = max(x + 1, clone[i].ff);
        adj[mx].pb(clone[i].ss);
        st.insert(mx);
    }
    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

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	326 ms	9692 KB	Output is correct
2	Correct	330 ms	9572 KB	Output is correct
3	Correct	322 ms	9572 KB	Output is correct
4	Correct	327 ms	9704 KB	Output is correct
5	Correct	334 ms	9576 KB	Output is correct
6	Correct	331 ms	9580 KB	Output is correct
7	Correct	332 ms	9596 KB	Output is correct
8	Correct	331 ms	9576 KB	Output is correct
9	Correct	412 ms	8616 KB	Output is correct
10	Correct	419 ms	8380 KB	Output is correct
11	Correct	234 ms	8252 KB	Output is correct
12	Correct	536 ms	13984 KB	Output is correct
13	Correct	814 ms	19424 KB	Output is correct
14	Execution timed out	1073 ms	24900 KB	Time limit exceeded
15	Execution timed out	1097 ms	26752 KB	Time limit exceeded
16	Execution timed out	1092 ms	31380 KB	Time limit exceeded
17	Execution timed out	1089 ms	36116 KB	Time limit exceeded
18	Execution timed out	1043 ms	40852 KB	Time limit exceeded
19	Execution timed out	1084 ms	45540 KB	Time limit exceeded
20	Execution timed out	1091 ms	36048 KB	Time limit exceeded