Submission #637818

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
637818	2022-09-03T11:10:19 Z	beaconmc	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	405 ms	13848 KB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=(x); i<(y); i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll int

ll temp;
ll n,d,m;
ll lis[1000001];
vector<pair<ll,ll>> sus;

bool check(ll x){
	ll cur = 0;
	FOR(i,0,m){
		cur += lis[i];
		cur -= min(cur,x);
		if (cur > x*d){
			return false;
		}
	}
	return true;
}

void ans(ll x){
	vector<ll> realsus;
	queue<pair<ll,ll>> q;
	ll cur = 0;
	FOR(i,0,n){
		while (cur<m && sus[cur].first == i+1){
			q.push(sus[cur]);
			cur++;
		}

		ll sus = q.size();
		sus = min(sus,x);


		FOR(j,0,sus){
			cout << q.front().second << " ";
			q.pop();
		}
		cout << 0 << "\n";

	}
}

int main(){
	cin >> n >> d >> m;

	FOR(i,0,m){
		cin >> temp;
		lis[temp-1] += 1;

		sus.push_back(make_pair(temp,i+1));
	}
	sort(sus.begin(),sus.end());

	ll lo = 0;
	ll hi = 1000001;

	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}else{
			lo = mid+1;
		}
	}
	cout << lo << "\n";
	ans(lo);

	


	

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2576 KB	Output is correct
2	Correct	31 ms	2524 KB	Output is correct
3	Correct	31 ms	2496 KB	Output is correct
4	Correct	31 ms	2504 KB	Output is correct
5	Correct	30 ms	2516 KB	Output is correct
6	Correct	31 ms	2480 KB	Output is correct
7	Correct	30 ms	2492 KB	Output is correct
8	Correct	30 ms	2444 KB	Output is correct
9	Correct	43 ms	2108 KB	Output is correct
10	Correct	43 ms	1908 KB	Output is correct
11	Correct	40 ms	1712 KB	Output is correct
12	Correct	81 ms	3336 KB	Output is correct
13	Correct	121 ms	4696 KB	Output is correct
14	Correct	177 ms	6536 KB	Output is correct
15	Correct	200 ms	7724 KB	Output is correct
16	Correct	287 ms	9300 KB	Output is correct
17	Correct	308 ms	10736 KB	Output is correct
18	Correct	331 ms	12324 KB	Output is correct
19	Correct	405 ms	13848 KB	Output is correct
20	Correct	307 ms	10844 KB	Output is correct