Submission #494572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494572	2021-12-15T18:27:57 Z	idip	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	260 ms	13732 KB

jobs

#define LOCAL
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
    out << "(" << a.first << "," << a.second << ")";
    return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
    out << "["; bool first = true;
    for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
    return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
    out << "["; bool first = true;
    for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
    return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
    out << "{"; bool first = true;
    for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
    return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
    out << "{"; bool first = true;
    for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
    return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

typedef pair<int, int> pii;
using ll = long long;
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
// const int MOD = 998244353;

int n, d, m;
vector<pii> a;

bool check(int x) {
    int curr = 1, res = x;
    for (auto& i : a) {
        if (curr > i.first + d) return false;
        while (curr < i.first) {
            curr++;
            res = x;
        }
        res--;
        if (res == 0) {
            curr++;
            res = x;
        }
    }
    return true;
}

void print(int x) {
    int curr = 1, res = x;
    for (auto& i : a) {
        while (curr < i.first || res == 0) {
            cout << "0" << "\n";
            curr++;
            res = x;
        } 
        cout << i.second << " ";
        res--;
    }
    while (curr <= n) {
        curr++;
        cout << "0" << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
    cin >> n >> d >> m;
    a.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a.begin(), a.end());
    int low = 0, high = m;
    while (low != high - 1) {
        int mid = (low + high) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    cout << high << "\n";
    print(high);
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1612 KB	Output is correct
2	Correct	20 ms	1608 KB	Output is correct
3	Correct	18 ms	1740 KB	Output is correct
4	Correct	21 ms	1668 KB	Output is correct
5	Correct	19 ms	1628 KB	Output is correct
6	Correct	19 ms	1644 KB	Output is correct
7	Correct	18 ms	1684 KB	Output is correct
8	Correct	17 ms	1612 KB	Output is correct
9	Correct	29 ms	2008 KB	Output is correct
10	Correct	40 ms	1860 KB	Output is correct
11	Correct	25 ms	1624 KB	Output is correct
12	Correct	53 ms	3168 KB	Output is correct
13	Correct	78 ms	4588 KB	Output is correct
14	Correct	107 ms	6140 KB	Output is correct
15	Correct	127 ms	7516 KB	Output is correct
16	Correct	159 ms	9116 KB	Output is correct
17	Correct	188 ms	10532 KB	Output is correct
18	Correct	233 ms	12096 KB	Output is correct
19	Correct	260 ms	13732 KB	Output is correct
20	Correct	187 ms	10612 KB	Output is correct