oj.uz

답안 #443761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443761 2021-07-12T03:13:35 Z BackNoob Job Scheduling (CEOI12_jobs) C++14
40 / 100
 52 ms 6952 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 = 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

# 결과 실행 시간 메모리 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