Submission #450357

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450357	2021-08-02T15:34:15 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	1000 ms	45152 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	357 ms	9148 KB	Output isn't correct
2	Incorrect	352 ms	9020 KB	Output isn't correct
3	Incorrect	368 ms	9024 KB	Output isn't correct
4	Incorrect	349 ms	8908 KB	Output isn't correct
5	Incorrect	357 ms	8984 KB	Output isn't correct
6	Incorrect	352 ms	9020 KB	Output isn't correct
7	Incorrect	360 ms	9020 KB	Output isn't correct
8	Incorrect	355 ms	8908 KB	Output isn't correct
9	Incorrect	426 ms	8504 KB	Output isn't correct
10	Incorrect	420 ms	8384 KB	Output isn't correct
11	Correct	238 ms	8252 KB	Output is correct
12	Correct	547 ms	13596 KB	Output is correct
13	Incorrect	822 ms	18928 KB	Output isn't correct
14	Execution timed out	1087 ms	24536 KB	Time limit exceeded
15	Execution timed out	1091 ms	26408 KB	Time limit exceeded
16	Execution timed out	1078 ms	30996 KB	Time limit exceeded
17	Execution timed out	1091 ms	35732 KB	Time limit exceeded
18	Execution timed out	1090 ms	40468 KB	Time limit exceeded
19	Execution timed out	1095 ms	45152 KB	Time limit exceeded
20	Execution timed out	1095 ms	35752 KB	Time limit exceeded