oj.uz

Submission #873394

# Submission time Handle Problem Language Result Execution time Memory
873394 2023-11-15T02:26:27 Z bobbilyking Job Scheduling (CEOI12_jobs) C++17
0 / 100
 123 ms 65536 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 long long 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 1000010
#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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 51672 KB Memory limit exceeded
2 Runtime error 24 ms 51408 KB Memory limit exceeded
3 Runtime error 25 ms 51780 KB Memory limit exceeded
4 Runtime error 25 ms 51672 KB Memory limit exceeded
5 Runtime error 26 ms 51416 KB Memory limit exceeded
6 Runtime error 27 ms 51576 KB Memory limit exceeded
7 Runtime error 24 ms 51672 KB Memory limit exceeded
8 Runtime error 25 ms 51668 KB Memory limit exceeded
9 Runtime error 28 ms 50912 KB Memory limit exceeded
10 Runtime error 29 ms 51028 KB Memory limit exceeded
11 Runtime error 26 ms 50780 KB Memory limit exceeded
12 Runtime error 37 ms 53844 KB Memory limit exceeded
13 Runtime error 52 ms 59220 KB Memory limit exceeded
14 Runtime error 73 ms 62376 KB Memory limit exceeded
15 Runtime error 75 ms 62292 KB Memory limit exceeded
16 Runtime error 123 ms 65536 KB Memory limit exceeded
17 Runtime error 74 ms 65536 KB Execution killed with signal 9
18 Runtime error 78 ms 65536 KB Execution killed with signal 9
19 Runtime error 89 ms 65536 KB Execution killed with signal 9
20 Runtime error 78 ms 65536 KB Execution killed with signal 9