Submission #453763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453763	2021-08-04T17:31:48 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	1000 ms	49024 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 = 5e5 + 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

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	16956 KB	Output is correct
2	Correct	116 ms	17020 KB	Output is correct
3	Correct	114 ms	16924 KB	Output is correct
4	Correct	113 ms	16972 KB	Output is correct
5	Correct	114 ms	16904 KB	Output is correct
6	Correct	143 ms	16956 KB	Output is correct
7	Correct	123 ms	17128 KB	Output is correct
8	Correct	115 ms	17024 KB	Output is correct
9	Correct	261 ms	16956 KB	Output is correct
10	Correct	263 ms	16948 KB	Output is correct
11	Correct	110 ms	16700 KB	Output is correct
12	Correct	220 ms	21372 KB	Output is correct
13	Correct	338 ms	27184 KB	Output is correct
14	Correct	499 ms	31552 KB	Output is correct
15	Runtime error	570 ms	33872 KB	Memory limit exceeded
16	Runtime error	748 ms	38676 KB	Memory limit exceeded
17	Runtime error	870 ms	46936 KB	Memory limit exceeded
18	Execution timed out	1027 ms	48428 KB	Time limit exceeded
19	Execution timed out	1081 ms	49024 KB	Time limit exceeded
20	Runtime error	868 ms	46824 KB	Memory limit exceeded