Submission #443753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443753	2021-07-12T02:59:44 Z	BackNoob	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	223 ms	9924 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 + 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

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	39 ms	7364 KB	Output isn't correct
2	Incorrect	30 ms	7304 KB	Output isn't correct
3	Incorrect	37 ms	7372 KB	Output isn't correct
4	Incorrect	33 ms	7356 KB	Output isn't correct
5	Incorrect	33 ms	7360 KB	Output isn't correct
6	Incorrect	34 ms	7364 KB	Output isn't correct
7	Incorrect	36 ms	7372 KB	Output isn't correct
8	Incorrect	37 ms	7360 KB	Output isn't correct
9	Incorrect	50 ms	9924 KB	Output isn't correct
10	Incorrect	50 ms	9884 KB	Output isn't correct
11	Incorrect	128 ms	7188 KB	Output isn't correct
12	Correct	223 ms	9572 KB	Output is correct
13	Incorrect	22 ms	7176 KB	Output isn't correct
14	Incorrect	27 ms	7232 KB	Output isn't correct
15	Incorrect	25 ms	7108 KB	Output isn't correct
16	Incorrect	59 ms	7176 KB	Output isn't correct
17	Incorrect	39 ms	7180 KB	Output isn't correct
18	Incorrect	23 ms	7208 KB	Output isn't correct
19	Incorrect	34 ms	7340 KB	Output isn't correct
20	Incorrect	50 ms	7236 KB	Output isn't correct