oj.uz

답안 #1053619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053619 2024-08-11T14:29:16 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 151 ms 17236 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int n,d,m;
pii a[1000010];

bool ok(int x)
{
	int t=0,i=0,cnt=0,mx=0;
	while(i<m)
	{
		while(i<m && cnt<x && a[i].fi<=t) mx=max(mx,t-a[i].fi),i++,cnt++;
		cnt=0;
		t++;
	}
	return mx<=d;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>d>>m;
	for(int i=0;i<m;i++) cin>>a[i].fi;
	for(int i=0;i<m;i++) a[i].se=i;
	sort(a,a+m);
	int l=1,r=m,ans=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(ok(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<'\n';
	int t=1,i=0,cnt=0;
	while(i<m)
	{
		while(i<m && cnt<ans && a[i].fi<=t)
		{
			cout<<a[i].se+1<<' ';
			i++,cnt++;
		}
		cnt=0;
		t++;
		cout<<"0\n";
	}
	while(t<=n) 
	{
		t++;
		cout<<"0\n";
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3416 KB Output is correct
2 Correct 10 ms 3472 KB Output is correct
3 Correct 10 ms 3416 KB Output is correct
4 Correct 10 ms 3508 KB Output is correct
5 Correct 10 ms 3416 KB Output is correct
6 Correct 10 ms 3420 KB Output is correct
7 Correct 10 ms 3508 KB Output is correct
8 Correct 10 ms 3420 KB Output is correct
9 Correct 16 ms 3696 KB Output is correct
10 Correct 17 ms 3672 KB Output is correct
11 Correct 16 ms 3420 KB Output is correct
12 Correct 31 ms 4692 KB Output is correct
13 Correct 56 ms 7732 KB Output is correct
14 Correct 65 ms 9300 KB Output is correct
15 Correct 91 ms 9816 KB Output is correct
16 Correct 113 ms 13684 KB Output is correct
17 Correct 116 ms 14928 KB Output is correct
18 Correct 128 ms 15184 KB Output is correct
19 Correct 151 ms 17236 KB Output is correct
20 Correct 120 ms 14928 KB Output is correct