oj.uz

답안 #443757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443757 2021-07-12T03:04:41 Z BackNoob Job Scheduling (CEOI12_jobs) C++14
10 / 100
 239 ms 9676 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(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

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