oj.uz

Submission #934419

# Submission time Handle Problem Language Result Execution time Memory
934419 2024-02-27T10:06:55 Z tamir1 Job Scheduling (CEOI12_jobs) C++14
30 / 100
 196 ms 23636 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
ll i,n,d,m,l,r,mid,ans;
pair<ll,ll> a[1000005];
bool check(ll mid){
	ll i,j,day=0;
	i=1;
	while(i<=m){
		day++;
		for(j=i;j<i+mid && j<=m;j++){
			if(day>=a[j].ff+d) return 0;
		}
		i=j;
	}
	if(day>n) return 0;
	return 1;
}
void solve(ll x){
	ll i,j,day=0;
	for(i=1;i<=m;){
		day++;
		for(j=i;j<i+x && j<=m;j++){
			cout << a[j].ss << " ";
		}
		i=j;
		cout << 0 << "\n";
	}
	for(i=day+1;i<=n;i++){
		cout << 0 << "\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> d >> m;
	for(i=1;i<=m;i++){
		cin >> a[i].ff;
		a[i].ss=i;
	}
	sort(a+1,a+m+1);
	l=1;
	r=m;
	while(r-l>1){
		mid=(r+l+1)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	if(check(l)) ans=l;
	else ans=r;
	cout << ans << "\n";
	solve(ans);
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3496 KB Output isn't correct
2 Incorrect 13 ms 3416 KB Output isn't correct
3 Incorrect 14 ms 3420 KB Output isn't correct
4 Incorrect 13 ms 3420 KB Output isn't correct
5 Incorrect 13 ms 3532 KB Output isn't correct
6 Incorrect 14 ms 3628 KB Output isn't correct
7 Incorrect 14 ms 3420 KB Output isn't correct
8 Incorrect 15 ms 3420 KB Output isn't correct
9 Incorrect 23 ms 3500 KB Output isn't correct
10 Incorrect 24 ms 3668 KB Output isn't correct
11 Correct 21 ms 3416 KB Output is correct
12 Incorrect 43 ms 6640 KB Output isn't correct
13 Correct 62 ms 9448 KB Output is correct
14 Incorrect 85 ms 10580 KB Output isn't correct
15 Incorrect 101 ms 13392 KB Output isn't correct
16 Correct 131 ms 16776 KB Output is correct
17 Correct 152 ms 20052 KB Output is correct
18 Correct 177 ms 22352 KB Output is correct
19 Incorrect 196 ms 23636 KB Output isn't correct
20 Correct 152 ms 19880 KB Output is correct