oj.uz

답안 #390251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390251 2021-04-15T16:03:56 Z grobar Job Scheduling (CEOI12_jobs) C++14
100 / 100
 451 ms 17444 KB 
#include <bits/stdc++.h>

using namespace std;
int n,d,m;
int a[1000006];
vector< pair<int,int> >par;
bool works(int x)
{
    int curr=0;
    for(int day=0;day<n;day++)
    {
        for(int j=0;j<x;j++)
        {
            if(curr<m && par[curr].first<=day+1 && par[curr].first>=day+1-d)
            {
                curr++;
            }else
            {
                break;
            }
        }
    }
    if(curr==m)
    {
        return true;
    }else
    {
        return false;
    }
}
int main()
{
    cin>>n>>d>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a[i];
        par.push_back(make_pair(a[i],i+1));
    }
    sort(par.begin(),par.end());
    int low=0,high=m,mid,ans=-1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(works(mid)==true)
        {
            ans=mid;
            high=mid-1;
        }else
        {
            low=mid+1;
        }
    }
    cout<<ans<<endl;
    int cur = 0;
	for(int day=0;day<n;day++) {
        for(int i=0;i<ans;i++) {
            if(cur<m && par[cur].first<=day+1 && par[cur].first+d>=day+1) {
                printf("%d ",par[cur].second);
                cur++;
            }
            else break;
        }
        printf("0\n");
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2100 KB Output is correct
2 Correct 41 ms 2136 KB Output is correct
3 Correct 36 ms 2160 KB Output is correct
4 Correct 39 ms 2256 KB Output is correct
5 Correct 43 ms 2132 KB Output is correct
6 Correct 36 ms 2128 KB Output is correct
7 Correct 36 ms 2112 KB Output is correct
8 Correct 36 ms 2168 KB Output is correct
9 Correct 48 ms 2368 KB Output is correct
10 Correct 49 ms 2336 KB Output is correct
11 Correct 47 ms 2116 KB Output is correct
12 Correct 96 ms 4036 KB Output is correct
13 Correct 144 ms 5856 KB Output is correct
14 Correct 206 ms 7848 KB Output is correct
15 Correct 250 ms 9736 KB Output is correct
16 Correct 310 ms 11548 KB Output is correct
17 Correct 363 ms 13468 KB Output is correct
18 Correct 392 ms 15528 KB Output is correct
19 Correct 451 ms 17444 KB Output is correct
20 Correct 369 ms 13468 KB Output is correct