Submission #873395

#	Time	Username	Problem	Language	Result	Execution time	Memory
873395		bobbilyking	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	107 ms	22956 KiB

jobs

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
 
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
 
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
 
#define NN 100010
#define M 1000000007 // 998244353
 
ll n, d, m;
ll a[NN];
vector<ll> itemsAt[NN], sol[NN];
 
bool works(ll v, bool doit) {
    queue<pl> pq; // (day submitted, amnt rem)
    queue<ll> doitq;
 
    F(day, 1, n+1) {
        if (a[day]) {
            pq.emplace(day+d, a[day]);
            if (doit) for (auto x: itemsAt[day]) doitq.push(x);
        }
        ll avail = v;
        while (avail and pq.size()) {
            ll sub = min(avail, pq.front().V);
            pq.front().V -= sub; avail -= sub;
            if (pq.front().V == 0) pq.pop();
            if (doit) while (sub--) {
                sol[day].push_back(doitq.front()); doitq.pop();
            }
        }
        if (pq.size() and pq.front().K == day) return false;
    }
    return pq.empty();
}
 
int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);
 
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    cin >> n >> d >> m;
    F(i, 0, m) {
        G(x) a[x]++; itemsAt[x].push_back(i+1);
    }
    ll l = 0, r = m;
    while (l+1<r) {
        ll mid = (l+r)/2;
        if (works(mid, false)) r = mid;
        else l = mid;    
    }
    works(r, true);
    cout << r << '\n';
    F(i, 1, n+1) {
        for (auto x: sol[i]) cout << x << " "; cout << "0\n";
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:71:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |         for (auto x: sol[i]) cout << x << " "; cout << "0\n";
      |         ^~~
jobs.cpp:71:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   71 |         for (auto x: sol[i]) cout << x << " "; cout << "0\n";
      |                                                ^~~~

• Subtask 1: 100 / 100