Submission #450353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450353	2021-08-02T15:30:23 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1000 ms	45460 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;
    }
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	355 ms	9060 KB	Output isn't correct
2	Incorrect	356 ms	9144 KB	Output isn't correct
3	Incorrect	370 ms	9064 KB	Output isn't correct
4	Incorrect	359 ms	9160 KB	Output isn't correct
5	Incorrect	358 ms	9064 KB	Output isn't correct
6	Incorrect	361 ms	9056 KB	Output isn't correct
7	Incorrect	360 ms	9060 KB	Output isn't correct
8	Incorrect	358 ms	9064 KB	Output isn't correct
9	Incorrect	442 ms	8376 KB	Expected EOLN
10	Incorrect	429 ms	8400 KB	Expected EOLN
11	Incorrect	241 ms	8252 KB	Expected EOLN
12	Incorrect	555 ms	13980 KB	Expected EOLN
13	Incorrect	832 ms	19296 KB	Expected EOLN
14	Execution timed out	1091 ms	24256 KB	Time limit exceeded
15	Execution timed out	1084 ms	26664 KB	Time limit exceeded
16	Execution timed out	1089 ms	31464 KB	Time limit exceeded
17	Execution timed out	1086 ms	36120 KB	Time limit exceeded
18	Execution timed out	1095 ms	40844 KB	Time limit exceeded
19	Execution timed out	1089 ms	45460 KB	Time limit exceeded
20	Execution timed out	1089 ms	36120 KB	Time limit exceeded