Submission #494572

#	Time	Username	Problem	Language	Result	Execution time	Memory
494572		idip	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	260 ms	13732 KiB

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 / 100