Submission #825456

# Submission time Handle Problem Language Result Execution time Memory
825456 2023-08-14T20:42:57 Z Nelt Job Scheduling (CEOI12_jobs) C++17
55 / 100
123 ms 19676 KB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    ll n, d, m;
    cin >> n >> d >> m;
    ll cnt[n], a[n];
    vv(ll) v[n];
    memset(cnt, 0, sizeof(cnt));
    for (ll i = 0, x; i < m; i++)
        cin >> x, cnt[--x]++, v[x].pb(i + 1);
    memcpy(a, cnt, sizeof(a));
    ll l = 0, r = m, ans = m;
    while (l <= r)
    {
        ll mid = (l + r) >> 1, ptr = 0;
        bool ok = true;
        memcpy(cnt, a, sizeof(a));
        for (ll i = 0; i < n; i++)
        {
            if (i > d and cnt[i - d - 1])
            {
                ok = false;
                break;
            }
            for (ll j = 0; j < mid and ptr < n; j++)
            {
                while (ptr < n and !cnt[ptr])
                    ptr++;
                if (ptr < n)
                    cnt[ptr]--;
            }
        }
        ok &= !accumulate(all(cnt), 0);
        if (ok)
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    cout << ans << endl;
    ll ptr = 0;
    for (ll i = 0; i < n; i++)
        {
            for (ll j = 0; j < ans and ptr < n; j++)
            {
                while (ptr < n and v[ptr].empty())
                    ptr++;
                if (ptr < n)
                    cout << v[ptr].back() << " ", v[ptr].pop_back();
            }
            cout << "0\n";
        }
}

/*

*/
int main()
{
    ANDROID
    // precomp();
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2384 KB Output isn't correct
2 Incorrect 13 ms 2136 KB Output isn't correct
3 Incorrect 12 ms 2128 KB Output isn't correct
4 Incorrect 13 ms 2256 KB Output isn't correct
5 Incorrect 13 ms 2176 KB Output isn't correct
6 Incorrect 12 ms 2252 KB Output isn't correct
7 Incorrect 13 ms 2256 KB Output isn't correct
8 Incorrect 12 ms 2256 KB Output isn't correct
9 Correct 18 ms 6172 KB Output is correct
10 Correct 18 ms 6144 KB Output is correct
11 Correct 14 ms 2064 KB Output is correct
12 Correct 26 ms 3668 KB Output is correct
13 Correct 38 ms 6728 KB Output is correct
14 Correct 62 ms 8460 KB Output is correct
15 Incorrect 63 ms 9796 KB Output isn't correct
16 Correct 94 ms 12472 KB Output is correct
17 Correct 110 ms 15560 KB Output is correct
18 Correct 100 ms 15052 KB Output is correct
19 Correct 123 ms 19676 KB Output is correct
20 Correct 109 ms 15564 KB Output is correct