Submission #443761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443761	2021-07-12T03:13:35 Z	BackNoob	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	52 ms	6952 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define y1 BinhKhung
using namespace std;
const int mxN = 2e5 + 7;
const int inf = 1e9 + 7;
const ll mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int offset = 1e5;

int numday , maxday , numjob;
pair<int , int> job[mxN];
vector<int> ans[mxN];

bool ok(int x)
{
    int day = 1;
    for(int i = 1 ; i <= numday ; i++) {
        for(int j = 1 ; j <= x ; j++) {
            if(job[day].fi <= i && i <= job[i].fi + maxday) {
                day++;
                if(day > numjob) return true;
            }
            else break;
        }
    }
    return day > numjob;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);

    
    cin >> numday >> maxday >> numjob;

    for(int i = 1 ; i <= numjob ; i++) cin >> job[i].fi;
    for(int i = 1 ; i <= numjob ; i++) job[i].se = i;

    sort(job + 1 , job + 1 + numjob);

    int lo = 1 , hi = numjob;
    while(lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if(ok(m)) hi = m;
        else lo = m;
    }

    int res = 0;
    if(ok(lo)) res = lo;
    else res = hi;

    cout << res << endl;
    int day = 1;
    for(int i = 1 ; i <= numday ; i++) {
        for(int j = 1 ; j <= res ; j++) {
            if(job[day].fi <= i && i <= job[i].fi + maxday) {
                ans[i].push_back(job[day].se);
                day++;
                if(day > numjob) break;
            }
            else break;
        }
        if(day > numjob) break;
    }

    for(int i = 1 ; i <= numday ; i++) {
        for(int j : ans[i]) cout << j << ' ';
        cout << 0 << endl;
    }
    
    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6936 KB	Output is correct
2	Correct	28 ms	6820 KB	Output is correct
3	Correct	29 ms	6824 KB	Output is correct
4	Correct	28 ms	6852 KB	Output is correct
5	Correct	35 ms	6812 KB	Output is correct
6	Correct	28 ms	6860 KB	Output is correct
7	Correct	29 ms	6952 KB	Output is correct
8	Correct	30 ms	6892 KB	Output is correct
9	Incorrect	38 ms	6036 KB	Output isn't correct
10	Incorrect	37 ms	6084 KB	Output isn't correct
11	Incorrect	23 ms	5800 KB	Output isn't correct
12	Incorrect	52 ms	6740 KB	Output isn't correct
13	Incorrect	24 ms	6508 KB	Output isn't correct
14	Incorrect	23 ms	6604 KB	Output isn't correct
15	Incorrect	21 ms	6528 KB	Output isn't correct
16	Incorrect	27 ms	6560 KB	Output isn't correct
17	Incorrect	29 ms	6556 KB	Output isn't correct
18	Incorrect	22 ms	6604 KB	Output isn't correct
19	Incorrect	36 ms	6656 KB	Output isn't correct
20	Incorrect	24 ms	6524 KB	Output isn't correct