Submission #453766

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453766	2021-08-04T17:36:34 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1000 ms	40644 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 = 2e5 + 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) {
        rep(j, 0, adj[i].size()-1) cout << adj[i][j] << ' ';
        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	115 ms	9676 KB	Output is correct
2	Correct	110 ms	9672 KB	Output is correct
3	Correct	109 ms	9560 KB	Output is correct
4	Correct	110 ms	9680 KB	Output is correct
5	Correct	110 ms	9664 KB	Output is correct
6	Correct	110 ms	9676 KB	Output is correct
7	Correct	109 ms	9672 KB	Output is correct
8	Correct	110 ms	9568 KB	Output is correct
9	Correct	279 ms	9660 KB	Output is correct
10	Correct	264 ms	9704 KB	Output is correct
11	Correct	103 ms	9276 KB	Output is correct
12	Correct	226 ms	13708 KB	Output is correct
13	Correct	344 ms	19204 KB	Output is correct
14	Correct	517 ms	23788 KB	Output is correct
15	Correct	598 ms	26132 KB	Output is correct
16	Correct	727 ms	30744 KB	Output is correct
17	Runtime error	871 ms	38936 KB	Memory limit exceeded
18	Execution timed out	1029 ms	40644 KB	Time limit exceeded
19	Execution timed out	1074 ms	33780 KB	Time limit exceeded
20	Runtime error	879 ms	38976 KB	Memory limit exceeded