답안 #956204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956204 2024-04-01T10:03:58 Z steveonalex Job Scheduling (CEOI12_jobs) C++17
100 / 100
191 ms 22096 KB
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69;
vector<pair<int, int>> createQuery[N];
int destroyQuery[N];

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

    int n, d, m; cin >> n >> d >> m;
    vector<int> a(m);
    for(int i = 0; i<m; ++i) cin >> a[i];

    for(int i = 0; i<m; ++i) {
        createQuery[a[i]].push_back({a[i] + d, i+1});
        destroyQuery[a[i] + d]++;
    }

    int l = 1, r = m;
    while(l < r){
        int mid = (l + r) >> 1;
        bool check = true;
        int sum1 = 0, cur = 0, sum2 = 0;
        for(int i = 1; i<=n; ++i){
            sum1 += createQuery[i].size();
            sum2 += destroyQuery[i];
            cur = min(sum1, cur + mid);
            if (cur < sum2) {check = false; break;}
        }

        if (check) r = mid;
        else l = mid + 1;
    }

    int x = l;
    cout << x << "\n";

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i<=n; ++i){
        for(auto j: createQuery[i]) pq.push(j);
        for(int j = 0; j < x; ++j){
            if (pq.empty()) break;
            pair<int, int> cur = pq.top(); pq.pop();
            cout << cur.second << " ";
        }
        cout << 0 << "\n";
    }

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5712 KB Output is correct
2 Correct 21 ms 5844 KB Output is correct
3 Correct 21 ms 5724 KB Output is correct
4 Correct 22 ms 5844 KB Output is correct
5 Correct 21 ms 5724 KB Output is correct
6 Correct 20 ms 5724 KB Output is correct
7 Correct 26 ms 5724 KB Output is correct
8 Correct 21 ms 5712 KB Output is correct
9 Correct 24 ms 5468 KB Output is correct
10 Correct 26 ms 5468 KB Output is correct
11 Correct 22 ms 4956 KB Output is correct
12 Correct 50 ms 7376 KB Output is correct
13 Correct 61 ms 10580 KB Output is correct
14 Correct 102 ms 12804 KB Output is correct
15 Correct 84 ms 14420 KB Output is correct
16 Correct 103 ms 17040 KB Output is correct
17 Correct 143 ms 20560 KB Output is correct
18 Correct 171 ms 20672 KB Output is correct
19 Correct 191 ms 22096 KB Output is correct
20 Correct 129 ms 20620 KB Output is correct