oj.uz

답안 #443763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443763 2021-07-12T03:22:17 Z BackNoob Job Scheduling (CEOI12_jobs) C++14
70 / 100
 327 ms 41284 KB 
#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 = 1e6 + 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[day].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[day].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
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 25676 KB Output is correct
2 Correct 39 ms 25636 KB Output is correct
3 Correct 38 ms 25668 KB Output is correct
4 Correct 38 ms 25712 KB Output is correct
5 Correct 40 ms 25668 KB Output is correct
6 Correct 40 ms 25632 KB Output is correct
7 Correct 39 ms 25708 KB Output is correct
8 Correct 39 ms 25720 KB Output is correct
9 Correct 56 ms 25792 KB Output is correct
10 Correct 55 ms 25864 KB Output is correct
11 Correct 47 ms 25668 KB Output is correct
12 Correct 80 ms 27668 KB Output is correct
13 Correct 116 ms 30132 KB Output is correct
14 Correct 154 ms 32300 KB Output is correct
15 Runtime error 181 ms 33080 KB Memory limit exceeded
16 Runtime error 219 ms 35268 KB Memory limit exceeded
17 Runtime error 257 ms 39060 KB Memory limit exceeded
18 Runtime error 285 ms 39620 KB Memory limit exceeded
19 Runtime error 327 ms 41284 KB Memory limit exceeded
20 Runtime error 267 ms 39236 KB Memory limit exceeded