답안 #1027558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027558 2024-07-19T07:31:22 Z vjudge1 Job Scheduling (CEOI12_jobs) C++14
100 / 100
234 ms 31316 KB
#include <bits/stdc++.h>

using namespace std;
long long n,m,d;
const long long MAX=1e5+10;
const long long MMAX=1e6+10;
pair<long long,long long> niza[MMAX];
vector<long long> v[MAX];
bool can(long long x)
{
    if(x<=0)return false;
    if(x>=m)return true;
    long long i=0;

    for(long long day=1; day<=n; day++)
    {
        long long cnt=0;
        while(i<m)
        {
            if(niza[i].first+d<day)return false;
            else if(niza[i].first>day)break;
            cnt++;
            i++;
            if(cnt==x)break;
        }
    }
    if(i>=m)return true;
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>d>>m;
    for(long long i=0; i<m; i++)
    {
        cin>>niza[i].first;
        niza[i].second=i+1;
    }
    sort(niza,niza+m);
    long long b=0,e=m;
    long long res=m;
    while(b<=e)
    {
        long long mid=(b+e)/2;
        if(can(mid))
        {
            res=mid;
            e=mid-1;
        }
        else
        {
            b=mid+1;
        }
    }
    long long i=0;
    for(long long day=1; day<=n; day++)
    {
        long long cnt=0;
        while(i<m)
        {
            if(niza[i].first>day)break;
            v[day].push_back(niza[i].second);
            cnt++;
            i++;

            if(cnt==res)break;
        }


    }
    cout<<res<<endl;
    for(long long i=1; i<=n; i++)
    {
        for(auto x:v[i])
        {
            cout<<x<<" ";
        }
        cout<<0<<endl;
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 6240 KB Output is correct
2 Correct 23 ms 6240 KB Output is correct
3 Correct 22 ms 6236 KB Output is correct
4 Correct 23 ms 6240 KB Output is correct
5 Correct 22 ms 6240 KB Output is correct
6 Correct 22 ms 6240 KB Output is correct
7 Correct 22 ms 6240 KB Output is correct
8 Correct 23 ms 6284 KB Output is correct
9 Correct 118 ms 6280 KB Output is correct
10 Correct 115 ms 6324 KB Output is correct
11 Correct 20 ms 6236 KB Output is correct
12 Correct 41 ms 9864 KB Output is correct
13 Correct 61 ms 14676 KB Output is correct
14 Correct 91 ms 18516 KB Output is correct
15 Correct 98 ms 18304 KB Output is correct
16 Correct 130 ms 22096 KB Output is correct
17 Correct 141 ms 29576 KB Output is correct
18 Correct 165 ms 30600 KB Output is correct
19 Correct 234 ms 31316 KB Output is correct
20 Correct 142 ms 29580 KB Output is correct