Submission #453768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453768	2021-08-04T17:42:41 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1000 ms	39528 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 = 101000;
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.emplace(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.emplace(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.emplace(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.emplace(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	109 ms	7340 KB	Output is correct
2	Correct	110 ms	7228 KB	Output is correct
3	Correct	108 ms	7352 KB	Output is correct
4	Correct	109 ms	7352 KB	Output is correct
5	Correct	109 ms	7348 KB	Output is correct
6	Correct	110 ms	7352 KB	Output is correct
7	Correct	110 ms	7356 KB	Output is correct
8	Correct	108 ms	7232 KB	Output is correct
9	Correct	256 ms	7228 KB	Output is correct
10	Correct	258 ms	7324 KB	Output is correct
11	Correct	104 ms	6968 KB	Output is correct
12	Correct	216 ms	11408 KB	Output is correct
13	Correct	330 ms	16864 KB	Output is correct
14	Correct	492 ms	21464 KB	Output is correct
15	Correct	562 ms	23860 KB	Output is correct
16	Correct	737 ms	28424 KB	Output is correct
17	Runtime error	869 ms	36608 KB	Memory limit exceeded
18	Runtime error	998 ms	38276 KB	Memory limit exceeded
19	Execution timed out	1100 ms	39528 KB	Time limit exceeded
20	Runtime error	866 ms	36572 KB	Memory limit exceeded