oj.uz

Submission #873395

# Submission time Handle Problem Language Result Execution time Memory
873395 2023-11-15T02:28:41 Z bobbilyking Job Scheduling (CEOI12_jobs) C++17
100 / 100
 107 ms 22956 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7128 KB Output is correct
2 Correct 13 ms 6996 KB Output is correct
3 Correct 13 ms 7132 KB Output is correct
4 Correct 12 ms 7128 KB Output is correct
5 Correct 12 ms 7132 KB Output is correct
6 Correct 12 ms 7132 KB Output is correct
7 Correct 12 ms 7132 KB Output is correct
8 Correct 12 ms 7132 KB Output is correct
9 Correct 16 ms 7004 KB Output is correct
10 Correct 16 ms 6960 KB Output is correct
11 Correct 13 ms 6748 KB Output is correct
12 Correct 23 ms 8540 KB Output is correct
13 Correct 36 ms 11344 KB Output is correct
14 Correct 60 ms 13076 KB Output is correct
15 Correct 56 ms 13136 KB Output is correct
16 Correct 87 ms 16568 KB Output is correct
17 Correct 107 ms 22956 KB Output is correct
18 Correct 92 ms 21720 KB Output is correct
19 Correct 107 ms 22824 KB Output is correct
20 Correct 98 ms 22868 KB Output is correct