Submission #453767

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453767	2021-08-04T17:38:30 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1000 ms	40844 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 = 110000;
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	106 ms	7484 KB	Output is correct
2	Correct	112 ms	7480 KB	Output is correct
3	Correct	121 ms	7568 KB	Output is correct
4	Correct	106 ms	7484 KB	Output is correct
5	Correct	108 ms	7564 KB	Output is correct
6	Correct	111 ms	7452 KB	Output is correct
7	Correct	109 ms	7484 KB	Output is correct
8	Correct	108 ms	7484 KB	Output is correct
9	Correct	261 ms	7432 KB	Output is correct
10	Correct	259 ms	7564 KB	Output is correct
11	Correct	102 ms	7192 KB	Output is correct
12	Correct	219 ms	11584 KB	Output is correct
13	Correct	332 ms	17108 KB	Output is correct
14	Correct	508 ms	21756 KB	Output is correct
15	Correct	557 ms	24032 KB	Output is correct
16	Correct	739 ms	28568 KB	Output is correct
17	Runtime error	863 ms	36904 KB	Memory limit exceeded
18	Runtime error	992 ms	38508 KB	Memory limit exceeded
19	Execution timed out	1098 ms	40844 KB	Time limit exceeded
20	Runtime error	868 ms	36888 KB	Memory limit exceeded