답안 #1011792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011792	2024-07-01T08:28:16 Z	Ludissey	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	191 ms	24364 KB

jobs

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;
 
int n,d,m;
vector<pair<int,int>> s;

bool f(int x){
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        if(s[j].first>i) continue;
        int k=0;
        for (k = j; k<j+x&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
        }
        j=k;  
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> m;
    s.resize(m);
    for (int i = 0; i < m; i++) cin >> s[i].first;
    for (int i = 0; i < m; i++) s[i].second=i;

    sort(all(s));
    int l=0;
    int r=m;
    while(l<r){
        int mid=(l+r)/2;
        if(f(mid)) r=mid;
        else l=mid+1;
    }
    cout << l << "\n";
    int j=0;
    for (int i = 1; i <= n; i++)
    {   
        int k=0;
        for (k = j; k<j+l&&k<m; k++)
        {
            if(s[k].first>i) { k++; break; } 
            if(s[k].first+d<i) return false;
            cout << s[k].second+1 << " ";
        }
        cout << "0\n";
        j=k;  
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	2836 KB	Output is correct
2	Correct	12 ms	2908 KB	Output is correct
3	Correct	15 ms	2904 KB	Output is correct
4	Correct	13 ms	2840 KB	Output is correct
5	Correct	12 ms	2908 KB	Output is correct
6	Correct	12 ms	2892 KB	Output is correct
7	Correct	13 ms	2840 KB	Output is correct
8	Correct	15 ms	2780 KB	Output is correct
9	Correct	28 ms	2908 KB	Output is correct
10	Correct	21 ms	2908 KB	Output is correct
11	Correct	19 ms	2908 KB	Output is correct
12	Correct	38 ms	5492 KB	Output is correct
13	Correct	59 ms	8276 KB	Output is correct
14	Correct	81 ms	11088 KB	Output is correct
15	Correct	97 ms	13392 KB	Output is correct
16	Correct	123 ms	16748 KB	Output is correct
17	Correct	144 ms	19536 KB	Output is correct
18	Correct	165 ms	21328 KB	Output is correct
19	Correct	191 ms	24364 KB	Output is correct
20	Correct	145 ms	19540 KB	Output is correct