Submission #783505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783505	2023-07-15T01:59:03 Z	horiiseun	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	105 ms	13440 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(j);
        }
        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 = 1e6 + 5;
    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";
    }

}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	4052 KB	Output isn't correct
2	Incorrect	16 ms	3984 KB	Output isn't correct
3	Incorrect	16 ms	4052 KB	Output isn't correct
4	Incorrect	17 ms	4052 KB	Output isn't correct
5	Incorrect	16 ms	4056 KB	Output isn't correct
6	Incorrect	17 ms	4020 KB	Output isn't correct
7	Incorrect	16 ms	4028 KB	Output isn't correct
8	Incorrect	16 ms	4052 KB	Output isn't correct
9	Incorrect	18 ms	4028 KB	Output isn't correct
10	Incorrect	20 ms	4052 KB	Output isn't correct
11	Incorrect	13 ms	3796 KB	Output isn't correct
12	Incorrect	25 ms	4932 KB	Output isn't correct
13	Incorrect	37 ms	6872 KB	Output isn't correct
14	Incorrect	58 ms	7964 KB	Output isn't correct
15	Incorrect	57 ms	9052 KB	Output isn't correct
16	Incorrect	80 ms	10748 KB	Output isn't correct
17	Incorrect	98 ms	12592 KB	Output isn't correct
18	Incorrect	97 ms	12692 KB	Output isn't correct
19	Incorrect	105 ms	13440 KB	Output isn't correct
20	Incorrect	95 ms	12608 KB	Output isn't correct