oj.uz

답안 #1088328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088328 2024-09-14T08:51:25 Z metelkov Job Scheduling (CEOI12_jobs) C++17
100 / 100
 221 ms 23944 KB 
#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

# 결과 실행 시간 메모리 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