Submission #443757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443757	2021-07-12T03:04:41 Z	BackNoob	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	239 ms	9676 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(i >= job[day].fi && job[day].fi <= i + maxday) {
                day++;
                if(day > numjob) return true;
            }
        }
    }
    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 + maxday) {
                ans[i].push_back(job[day].se);
                day++;
                if(day > numjob) 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

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	7108 KB	Output isn't correct
2	Incorrect	29 ms	7084 KB	Output isn't correct
3	Incorrect	30 ms	7088 KB	Output isn't correct
4	Incorrect	31 ms	7108 KB	Output isn't correct
5	Incorrect	32 ms	7008 KB	Output isn't correct
6	Incorrect	34 ms	7108 KB	Output isn't correct
7	Incorrect	35 ms	7128 KB	Output isn't correct
8	Incorrect	36 ms	7216 KB	Output isn't correct
9	Incorrect	48 ms	9676 KB	Output isn't correct
10	Incorrect	47 ms	9668 KB	Output isn't correct
11	Correct	127 ms	6824 KB	Output is correct
12	Correct	239 ms	8976 KB	Output is correct
13	Incorrect	21 ms	6556 KB	Output isn't correct
14	Incorrect	25 ms	6604 KB	Output isn't correct
15	Incorrect	21 ms	6552 KB	Output isn't correct
16	Incorrect	45 ms	6624 KB	Output isn't correct
17	Incorrect	40 ms	6592 KB	Output isn't correct
18	Incorrect	22 ms	6544 KB	Output isn't correct
19	Incorrect	30 ms	6724 KB	Output isn't correct
20	Incorrect	39 ms	6676 KB	Output isn't correct