Submission #1104713

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104713	2024-10-24T09:12:49 Z	Thunnus	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	194 ms	42312 KB

jobs

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()

signed main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int n, d, m;
    cin >> n >> d >> m;
    vector<pii> job(m);
    vvi d2i(n + 1);
    for(int i = 0; i < m; i++){
        cin >> job[i].fi;
        job[i].se;
        d2i[job[i].fi].emplace_back(i);
    }
    //sort(job.begin(), job.end());

    auto check = [&](int val) -> bool {
        deque<pii> dq;
        for(int day = 1; day <= n; day++){
            int temp = val;
            while(!dq.empty() && temp){
                pii cur = dq.front();
                dq.pop_front();
                if(cur.fi + d < day) return false;
                int minus = min(cur.se, temp);
                cur.se -= minus, temp -= minus;
                if(cur.se){
                    dq.emplace_front(cur);
                }
            }
            int rem = max(sz(d2i[day]) - temp, 0ll);
            if(rem){
                dq.emplace_back(day, rem);
            }
        }
        return (dq.empty());
    };

    auto bs = [&]() -> int {
        int lo = 1, hi = m, ret = 1, mid;
        while(hi >= lo){
            mid = lo + (hi - lo) / 2;
            if(check(mid)){
                hi = mid - 1;
                ret = mid;
            }
            else{
                lo = mid + 1;
            }
        }
        return ret;
    };

    int val = bs();
    vvi ans(n + 1);
    queue<int> q;
    for(int day = 1; day <= n; day++){
        for(int i = 0; i < val; i++){
            if(!q.empty()){
                ans[day].emplace_back(q.front() + 1);
                q.pop();
            }
            else if(sz(d2i[day])){
                ans[day].emplace_back(d2i[day].back() + 1);
                d2i[day].pop_back();
            }
            else break;
        }
    }

    for(int day = 1; day <= n; day++){
        for(int &i : ans[day]){
            cout << i << " ";
        }
        cout << "0\n";
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	4292 KB	Output isn't correct
2	Incorrect	16 ms	4292 KB	Output isn't correct
3	Incorrect	17 ms	4292 KB	Output isn't correct
4	Incorrect	17 ms	4300 KB	Output isn't correct
5	Incorrect	16 ms	4292 KB	Output isn't correct
6	Incorrect	16 ms	4292 KB	Output isn't correct
7	Incorrect	17 ms	4292 KB	Output isn't correct
8	Incorrect	17 ms	4292 KB	Output isn't correct
9	Incorrect	23 ms	9356 KB	Expected EOLN
10	Incorrect	41 ms	9288 KB	Expected EOLN
11	Incorrect	39 ms	4680 KB	Expected EOLN
12	Incorrect	40 ms	8520 KB	Expected EOLN
13	Incorrect	62 ms	15432 KB	Expected EOLN
14	Incorrect	120 ms	18892 KB	Expected EOLN
15	Incorrect	109 ms	21064 KB	Expected EOLN
16	Incorrect	156 ms	26452 KB	Expected EOLN
17	Runtime error	186 ms	34632 KB	Memory limit exceeded
18	Runtime error	174 ms	35584 KB	Memory limit exceeded
19	Runtime error	194 ms	42312 KB	Memory limit exceeded
20	Runtime error	177 ms	34628 KB	Memory limit exceeded