Submission #450354

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450354	2021-08-02T15:31:46 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	1000 ms	44808 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));
    sort(all(v));
    ll l = 0, r = n;
    while(l < r) {
        ll mid = (l + r) / 2;
        multiset<ll> st;
        rep(i, 0, mid - 1) st.insert(v[i]);
        bool ok = true;
        rep(i, mid, n - 1) {
            ll x = *st.begin();
            st.erase(st.begin());
            if(x > v[i] + delay) {
                ok = false;
                break;
            }
            else st.insert(max(x + 1, v[i]));
        }
        if(ok) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    sort(all(clone));
    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 + 1 << ' ';
        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

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	353 ms	8656 KB	Output isn't correct
2	Incorrect	373 ms	8888 KB	Output isn't correct
3	Incorrect	355 ms	8772 KB	Output isn't correct
4	Incorrect	361 ms	8820 KB	Output isn't correct
5	Incorrect	355 ms	8772 KB	Output isn't correct
6	Incorrect	360 ms	8824 KB	Output isn't correct
7	Incorrect	355 ms	8764 KB	Output isn't correct
8	Incorrect	366 ms	8764 KB	Output isn't correct
9	Incorrect	420 ms	8260 KB	Output isn't correct
10	Incorrect	434 ms	8164 KB	Output isn't correct
11	Correct	246 ms	7872 KB	Output is correct
12	Correct	553 ms	13336 KB	Output is correct
13	Incorrect	851 ms	18720 KB	Output isn't correct
14	Execution timed out	1086 ms	22620 KB	Time limit exceeded
15	Execution timed out	1093 ms	26140 KB	Time limit exceeded
16	Execution timed out	1086 ms	30740 KB	Time limit exceeded
17	Execution timed out	1091 ms	35500 KB	Time limit exceeded
18	Execution timed out	1088 ms	40196 KB	Time limit exceeded
19	Execution timed out	1092 ms	44808 KB	Time limit exceeded
20	Execution timed out	1084 ms	35644 KB	Time limit exceeded