Submission #443758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443758	2021-07-12T03:09:21 Z	BackNoob	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	1000 ms	6700 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;
            }
        }
    }
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1079 ms	5748 KB	Time limit exceeded
2	Execution timed out	1090 ms	5708 KB	Time limit exceeded
3	Execution timed out	1088 ms	5708 KB	Time limit exceeded
4	Execution timed out	1086 ms	5776 KB	Time limit exceeded
5	Execution timed out	1096 ms	5768 KB	Time limit exceeded
6	Execution timed out	1092 ms	5708 KB	Time limit exceeded
7	Execution timed out	1094 ms	5760 KB	Time limit exceeded
8	Execution timed out	1081 ms	5708 KB	Time limit exceeded
9	Execution timed out	1098 ms	5708 KB	Time limit exceeded
10	Execution timed out	1087 ms	5708 KB	Time limit exceeded
11	Execution timed out	1088 ms	5708 KB	Time limit exceeded
12	Execution timed out	1078 ms	6568 KB	Time limit exceeded
13	Incorrect	30 ms	6700 KB	Output isn't correct
14	Incorrect	34 ms	6592 KB	Output isn't correct
15	Incorrect	25 ms	6560 KB	Output isn't correct
16	Incorrect	458 ms	6560 KB	Output isn't correct
17	Incorrect	62 ms	6596 KB	Output isn't correct
18	Incorrect	40 ms	6572 KB	Output isn't correct
19	Execution timed out	1084 ms	6504 KB	Time limit exceeded
20	Incorrect	50 ms	6552 KB	Output isn't correct