Submission #783511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783511	2023-07-15T02:09:40 Z	horiiseun	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	165 ms	13420 KB

jobs

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <bitset>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
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 A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
    #define D(...)
#endif

int n, d, m, l, r, md;
vector<int> t[100005];
queue<int> q;

bool valid(int x) {
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) {
        for (int j : t[i]) {
            q.push(i);
        }
        for (int j = 0; j < x && !q.empty(); j++) {
            if (i - q.front() > d) {
                return false;
            }
            q.pop();
        }
    }
    if (!q.empty()) return false;
    return true;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> d >> m;
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        t[x].push_back(i);
    }

    l = 0, r = m;
    while (l + 1 != r) {
        md = (l + r) / 2;
        if (valid(md)) r = md;
        else l = md;
    }

    cout << r << "\n";

    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) {
        for (int j : t[i]) {
            q.push(j);
        }
        for (int j = 0; j < r && !q.empty(); j++) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << 0 << "\n";
    }

}

Compilation message

jobs.cpp: In function 'bool valid(int)':
jobs.cpp:122:18: warning: unused variable 'j' [-Wunused-variable]
  122 |         for (int j : t[i]) {
      |                  ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4052 KB	Output is correct
2	Correct	19 ms	4052 KB	Output is correct
3	Correct	23 ms	4072 KB	Output is correct
4	Correct	20 ms	4016 KB	Output is correct
5	Correct	19 ms	4052 KB	Output is correct
6	Correct	19 ms	4008 KB	Output is correct
7	Correct	19 ms	4052 KB	Output is correct
8	Correct	18 ms	4084 KB	Output is correct
9	Correct	25 ms	4092 KB	Output is correct
10	Correct	25 ms	4044 KB	Output is correct
11	Correct	19 ms	3792 KB	Output is correct
12	Correct	36 ms	4992 KB	Output is correct
13	Correct	54 ms	6872 KB	Output is correct
14	Correct	80 ms	8104 KB	Output is correct
15	Correct	85 ms	9040 KB	Output is correct
16	Correct	121 ms	10756 KB	Output is correct
17	Correct	138 ms	12664 KB	Output is correct
18	Correct	142 ms	12636 KB	Output is correct
19	Correct	165 ms	13420 KB	Output is correct
20	Correct	138 ms	12684 KB	Output is correct