Submission #416740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416740	2021-06-02T21:25:36 Z	winstonyin	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	481 ms	24096 KB

jobs

#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <map>
#include <set>
#include <fstream>
#include <unordered_map>
#include <queue>
using namespace std;
using pi = pair<int, int>;
using pd = pair<double, double>; 
#define ll long long
#define all(x) (x).begin(), (x).end()
ll  days, delay, requests;
vector<pair<ll,ll>> seq;
bool works(ll  machines) {
    if(days*machines < requests) {
        return false;
    }
    ll  cur_day = 0; ll  cur_req = 0;
    while(cur_day < days && cur_req < requests) {
        for(ll  j = 0; j < machines; j++) {
            if(cur_req == requests) {
                break;
            }
            if(seq[cur_req].first <= cur_day+1) {
                if(cur_day+1 - seq[cur_req].first <= delay) {
                    cur_req++;
                }
                else {
                    return false;
                }
            }
            else {
                break;
            }
        }
        cur_day++;
    }
    return cur_req == requests;
}
bool p_works(ll  machines) {
    if(days*machines < requests) {
        return false;
    }
    ll  cur_day = 0; ll  cur_req = 0;
    while(cur_day < days && cur_req < requests) {
        for(ll  j = 0; j < machines; j++) {
            if(cur_req == requests) {
                break;
            }
            if(seq[cur_req].first <= cur_day+1) {
                if(cur_day+1 - seq[cur_req].first <= delay) {
                    cout << seq[cur_req].second << " ";
                    cur_req++;
                }
                else {
                    return false;
                }
            }
            else {
                break;
            }
        }
        cout << 0 << endl;
        cur_day++;
    }
    return cur_req == requests;
}
int  main() {
    cin >> days >> delay >> requests;
    for(ll  i = 0; i < requests; i++) {
        ll  day; cin >> day;
        seq.push_back({day, i+1});
    }
    sort(all(seq));
    ll  a = 1, b = 1e9;
    ll  ans;
    while(a <= b) {
        ll  mid = (a+b)/2;
        // cout << a << " " << b << endl;
        if(works(mid)) {
            ans = mid;
            b = mid-1;
        }
        else {
            a = mid+1;
        }
    }
    p_works(ans);
    cout << ans;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	42 ms	2828 KB	Output isn't correct
2	Incorrect	42 ms	2780 KB	Output isn't correct
3	Incorrect	42 ms	2800 KB	Output isn't correct
4	Incorrect	49 ms	2788 KB	Output isn't correct
5	Incorrect	42 ms	2836 KB	Output isn't correct
6	Incorrect	42 ms	2788 KB	Output isn't correct
7	Incorrect	41 ms	2812 KB	Output isn't correct
8	Incorrect	47 ms	2772 KB	Output isn't correct
9	Incorrect	47 ms	2752 KB	Expected EOLN
10	Incorrect	47 ms	2716 KB	Expected EOLN
11	Incorrect	59 ms	2872 KB	Expected EOLN
12	Incorrect	106 ms	5564 KB	Expected EOLN
13	Incorrect	156 ms	9640 KB	Expected EOLN
14	Incorrect	236 ms	11296 KB	Expected EOLN
15	Incorrect	282 ms	13468 KB	Expected EOLN
16	Incorrect	367 ms	19480 KB	Expected EOLN
17	Incorrect	416 ms	19508 KB	Expected EOLN
18	Incorrect	438 ms	21548 KB	Expected EOLN
19	Incorrect	481 ms	24096 KB	Expected EOLN
20	Incorrect	412 ms	19444 KB	Expected EOLN