Submission #120989

#	Time	Username	Problem	Language	Result	Execution time	Memory
120989		MB81	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	358 ms	14408 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

queue <pii> q1;
vector <int> v1[maxn];
int n, d, m;

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		v1[x].PB(i + 1);
	}
	int l, r, mid;
	l = 0;
	r = m;
	while (r - l > 1) {
		mid = (l + r) >> 1;
		while(sz(q1)) q1.pop();
		bool ok = 1;
		for (int i = 1; i <= n; i++) {
			if (sz(q1) && q1.front().F < i - d)
				ok = 0;
			for (auto x : v1[i])
				q1.push(MP(i, x));
			for (int t = 0; t < mid && sz(q1); t++)
				q1.pop();
		}
		if (sz(q1))
			ok = 0;
		if (ok)	
			r = mid;
		else
			l = mid;
	}
	cout << r << "\n";
	while(sz(q1)) q1.pop();
	for (int i = 1; i <= n; i++) {
		for (auto x : v1[i])
			q1.push(MP(i, x));
		for (int t = 0; t < r && sz(q1); t++) {
			cout << q1.front().S << " ";
			q1.pop();
		}
		cout << "0\n";
	}

}

• Subtask 1: 100 / 100