oj.uz

답안 #572495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572495 2022-06-04T13:44:56 Z yhussain11 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 285 ms 22592 KB 
#include<bits/stdc++.h>

#define unless(x) if (!(x))
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;

// *INDENT-OFF*
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template<typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; }
template<size_t I = 0, typename... Tp> void __print_tup(const tuple<Tp...>& t) { cerr << get<I>(t); if constexpr(I < sizeof...(Tp) - 1) { cerr << ", "; __print_tup<I+1>(t); } }
template<typename... Tp> void __print(const tuple<Tp...>& t) { cerr << '{'; __print_tup(t); cerr << '}'; }
/* template<typename... Args> void __print(const tuple<Args...>& t) { cerr << '{'; apply([](auto&&... args) { ((cout << args << ','), ...); }, t); cerr << '}'; } */
template<typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
template<typename T> T ceil_div(T a, T b) { return (a + b - 1) / b; }
#ifdef LOCAL
#define dbg(x...) cerr << "\e[1;31m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[0m";
#else
#define dbg(x...)
#endif
// *INDENT-ON*

// YOU ARE ACTUALLY **SUPPOSED** TO READ THE FOLLOWING.
// Read the problem. Now Re-read the problem.
// Observe each constraint. Please do this. Notice each and every constraint.
// You have made many mistakes because you didn't read the constraint well enough.
// You are probably solving a harder version of the given problem.
// DO NOT OVERSOLVE.
// Do not look ahead for next problem. Solve the current problem.
// Do not look at standings.
// check overflow/underflow
// string(count, char)
// queue.push, queue.pop, queue.front, stack.push, stack.pop, stack.top
// string chk {x, y, x, y};
// string chk = string() + x + y + x + y;

void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vpi v(m);
    for (int i = 0; i < m; i++) {
        cin >> v[i].f;
        v[i].s = i;
    }
    sort(all(v));
    int lo = 1, hi = m;
    int mcnt = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int mx = 0;
        for (int i = 1, j = 0; i <= n; i++) {
            int cnt = 0;
            for (; j < m && cnt < mid && v[j].f <= i; j++) {
                cnt++;
                ckmax(mx, i - v[j].f);
            }
        }
        if (mx <= d) {
            mcnt = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    vector<vector<int>> ans(n);
    for (int i = 1, j = 0; i <= n; i++) {
        int cnt = 0;
        for (; j < m && cnt < mcnt && v[j].f <= i; j++) {
            cnt++;
            ans[i - 1].pb(v[j].s + 1);
        }
    }
    cout << mcnt << '\n';
    for (auto &x : ans) {
        for (auto &y : x) cout << y << " ";
        cout << 0 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 2764 KB Output is correct
2 Correct 23 ms 2700 KB Output is correct
3 Correct 24 ms 2700 KB Output is correct
4 Correct 20 ms 2776 KB Output is correct
5 Correct 22 ms 2660 KB Output is correct
6 Correct 26 ms 2668 KB Output is correct
7 Correct 29 ms 2656 KB Output is correct
8 Correct 21 ms 2684 KB Output is correct
9 Correct 42 ms 4936 KB Output is correct
10 Correct 44 ms 4940 KB Output is correct
11 Correct 33 ms 2588 KB Output is correct
12 Correct 58 ms 4888 KB Output is correct
13 Correct 106 ms 7764 KB Output is correct
14 Correct 155 ms 10860 KB Output is correct
15 Correct 154 ms 11572 KB Output is correct
16 Correct 233 ms 14396 KB Output is correct
17 Correct 232 ms 18296 KB Output is correct
18 Correct 231 ms 18868 KB Output is correct
19 Correct 285 ms 22592 KB Output is correct
20 Correct 228 ms 18336 KB Output is correct