Submission #774378

#	Time	Username	Problem	Language	Result	Execution time	Memory
774378		RonTheprogrammer	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	684 ms	52316 KiB

jobs

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <set>
#include <limits>
#include <string>
#include <deque>
#include <cassert>
#include <math.h>
#include <list>
#include<numeric>
#include<map>
#include<set>
//#include <bits/stdc++.h>

typedef long long ll;
const int maxn = 2e5 + 5;
const int MOD =(1e9 + 7);
const int INF = 1e9+1;
#define srt(a) sort(a.begin(),a.end());
#define rev(a) reverse(a.begin(),a.end());
#define eb(a) emplace_back(a);
#define nl "\n"

//typedef  {int, int} p;

using  namespace std;
/**/
struct DSU
{
	vector<int>parent;
	vector<int>size;

	void dsuinit(int n)
	{
		parent.resize(n);
		size.resize(n);
		for (int i = 0; i < n; i++)
		{
			make_set(i);
		}
	}

	int find_set(int v) {
		if (v == parent[v])
			return v;
		return parent[v] = find_set(parent[v]);
	}

	void make_set(int v)
	{
		parent[v] = v;
		size[v] = 1;
	}

	bool unite(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (size[a] < size[b])
				swap(a, b);
			parent[b] = a;
			size[a] += size[b];
			return true;
		}
		return false;
	}
};
int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e - 1);
}
int __gcd(int a, int b)
{
	if (b > a)
	{
		swap(a, b);
	}
	if (a % b == 0)
		return b;
	return __gcd(a, a % b);
}
ll __lcm(int a, int b)
{
	return ((ll)a *(ll)  b) / __gcd(a, b);
}
struct price {
	int cost, cnt;
	bool  operator < (const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
	bool compare(const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
};
struct range {
	int l, r, thief, change;
	bool operator <(const range& other) const
	{
		if (l == other.l)
			return r < other.r;
		return l < other.l;
	}

};
struct hole {
	int c1,  c2;
	ll w;
};

void solve() {
	int n, d, m; cin >> n >> d >> m;
	set<pair<int, int>> map;
	for (int i = 0; i < m; i++)
	{
		int t; cin >> t;
		map.insert({ t,i });
	}
	ll l = 0;
	ll r = 10;
	ll ans=1e12;
	while(l <r)
	{
		ll mid = (l + r) >>1 ;
		int t = 1;
		auto itr = map.begin();
		bool solve = true;
		int cnt = 0;
		while (itr != map.end())
		{
			if (cnt >= mid)
			{
				t++;
				cnt = 0;
			}
			if (t > itr->first + d)
			{
				solve = false;
				break;
			}
			else
			{
 				cnt++;
				itr++;
			}
		}
		if (solve) {
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << ans << nl;
	int cnt = 0;
	for (auto p : map)
	{
		if (cnt == ans)
		{
			cout << '0' << nl;
			cnt = 0;
		}
		cout << p.second + 1 << ' ';
		cnt++;
	}
	while (n >= ceil(m / ans)) {
		cout << '0' << nl;
		n--;
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	//freopen("wormsort.in", "r", stdin);
	//freopen("wormsort.out", "w", stdout);
	int t=1;
	while (t--)
		solve();
	return 0;

}
/**
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4




*/

• Subtask 1: 0 / 100