Submission #1088328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088328	2024-09-14T08:51:25 Z	metelkov	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	221 ms	23944 KB

jobs

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)

using ll = long long;
using ull = unsigned long long;

const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 998244353LL;

ll gcd(ll a, ll b) {
    if (a == 0LL) return b;
    return gcd(b % a, a);
}

vector<int> sieve(int n) {
    int sieve_size = n + 1;
    bool sieve[sieve_size];
    for (int i = 0; i < sieve_size; ++i) {
        sieve[i] = true;
    }

    for (int i = 2; i * i <= n; ++i) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i) {
                sieve[j] = false;
            }
        }
    }

    vector<int> ans;
    for (int i = 2; i <= n; ++i) {
        if (sieve[i]) {
            ans.push_back(i);
        }
    }
    return ans;
}

vector<ll> prime_factorization(ll n) {
    vector<ll> factors;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while(n % i == 0) {
                n /= i;
            }
            factors.push_back(i);
        }
    }

    if (n > 1) {
        factors.push_back(n);
    }
    
    return factors;
}

ll mod_multiplication(ll a, ll b) {
    return (((a * b) % MOD + MOD) % MOD);
}

ll mod_power(ll x, ll n) {
    ll res = 1LL;
    while(n > 0LL) {
        if(n % 2LL) {
            res = mod_multiplication(res, x);
        }
        x = mod_multiplication(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll a) {
    return mod_power(a, MOD - 2LL);
}

ll nCr(ll n, ll r) {
    ll res = 1LL, div = 1LL;
    for(ll i = 1 ; i <= r ; i++) {
        res = mod_multiplication(res, n - i + 1LL);
        div = mod_multiplication(div, i);
    }
    res = mod_multiplication(res, mod_inv(div));
    return res;
}

uint64_t inv(uint64_t a, uint64_t b) {
    return 1 < a ? b - inv(b % a, a) * b / a : 1;
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

uint32_t next_pow2(uint32_t x) { return x == 1 ? 1 : 1 << (32 - __builtin_clz(x - 1)); }

uint32_t next_pow(uint32_t x) { return x == 1 ? 0 : 32 - __builtin_clz(x - 1); }

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, d, m;
    cin >> n >> d >> m;

    pair<int, int> a[m];
    rep(i, m) {
        
        cin >> a[i].first;
        a[i].second = i + 1;
    }   

    sort(a, a + m);

    int left = 1;
    int right = m;
    int ans = right;

    while (left <= right) {

        int mid = (right - left) / 2 + left;

        queue<int> pq;
        int available = mid;
        bool ok = true;
        
        rep(i, m) {

            int timestamp = a[i].first;

            if (available) {

                pq.push(timestamp + 1);
                --available;
                continue;
            }

            if (pq.front() > timestamp + d) {

                ok = false;
                break;
            }

            int closest = pq.front();
            pq.pop();

            pq.push(max(closest + 1, timestamp + 1));
        }

        if (ok) {

            right = mid - 1;
            ans = min(mid, ans);
        } else {

            left = mid + 1;
        }
    }

    vector<int> by_days[n];

    int available = ans;
    queue<int> pq;
    
    rep(i, m) {

        int timestamp = a[i].first;
        int id = a[i].second;
        if (available) {

            by_days[timestamp - 1].push_back(id);

            pq.push(timestamp + 1);
            --available;
            continue;
        }

        int closest = pq.front();
        pq.pop();
        
        closest = max(closest, timestamp);
        by_days[closest - 1].push_back(id);
        pq.push(closest + 1);
    }

    cout << ans << '\n';

    rep(i, n) {

        for (auto j : by_days[i]) cout << j << ' ';
        cout << "0\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2904 KB	Output is correct
2	Correct	16 ms	2912 KB	Output is correct
3	Correct	15 ms	3012 KB	Output is correct
4	Correct	17 ms	3076 KB	Output is correct
5	Correct	17 ms	2884 KB	Output is correct
6	Correct	16 ms	2916 KB	Output is correct
7	Correct	15 ms	3120 KB	Output is correct
8	Correct	16 ms	3044 KB	Output is correct
9	Correct	24 ms	4872 KB	Output is correct
10	Correct	24 ms	5124 KB	Output is correct
11	Correct	22 ms	2556 KB	Output is correct
12	Correct	45 ms	5016 KB	Output is correct
13	Correct	70 ms	7784 KB	Output is correct
14	Correct	100 ms	10992 KB	Output is correct
15	Correct	116 ms	11472 KB	Output is correct
16	Correct	137 ms	14848 KB	Output is correct
17	Correct	174 ms	19264 KB	Output is correct
18	Correct	206 ms	19516 KB	Output is correct
19	Correct	221 ms	23944 KB	Output is correct
20	Correct	167 ms	19216 KB	Output is correct