oj.uz

답안 #443762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443762 2021-07-12T03:21:36 Z BackNoob Job Scheduling (CEOI12_jobs) C++14
60 / 100
 68 ms 8876 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[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
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 6904 KB Output is correct
2 Correct 29 ms 6816 KB Output is correct
3 Correct 29 ms 6816 KB Output is correct
4 Correct 27 ms 6980 KB Output is correct
5 Correct 26 ms 6884 KB Output is correct
6 Correct 27 ms 6900 KB Output is correct
7 Correct 27 ms 6876 KB Output is correct
8 Correct 28 ms 6952 KB Output is correct
9 Correct 44 ms 7108 KB Output is correct
10 Correct 43 ms 7124 KB Output is correct
11 Correct 35 ms 6864 KB Output is correct
12 Correct 68 ms 8876 KB Output is correct
13 Incorrect 25 ms 6556 KB Output isn't correct
14 Incorrect 23 ms 6604 KB Output isn't correct
15 Incorrect 21 ms 6488 KB Output isn't correct
16 Incorrect 24 ms 6636 KB Output isn't correct
17 Incorrect 27 ms 6528 KB Output isn't correct
18 Incorrect 27 ms 6584 KB Output isn't correct
19 Incorrect 29 ms 6776 KB Output isn't correct
20 Incorrect 24 ms 6604 KB Output isn't correct