Submission #1077105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077105		SeanCui	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	195 ms	16976 KiB

jobs

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <set>
#include <cstring>
#include <map>
#include <iomanip>
#include <string>
#include <queue>
#include <array>

using namespace std;

#define vi vector<int>
#define ll long long
#define pii pair<int, int>
#define mp make_pair	

const int mx = 1e5 + 1;
int a[mx], n, m, d;
vi tr[mx];

bool can(int x){
	queue<pii> q;
	for (int i = 1; i <= n; ++i){
		for (int j: tr[i])
			q.push(make_pair(j, i));
			
		int cnt = x;
		while ((cnt > 0) & (!q.empty())){
			pii temp = q.front();
			if (i - temp.second > d) return false;
			q.pop();
			--cnt;
		}
	}
	return true;
}

void solve(){
	cin >> n >> d >> m;
	for (int i = 1; i <= m; ++i){
		int x; cin >> x;
		++a[x];
		tr[x].push_back(i);
	}
	
	int l = 1, r = 1e5;
	while (l + 1 < r){
		int m = (l + r)/2;
		if (can(m)) r = m;
		else l = m;
	}	
	
	cout << r << "\n";
	
	queue<int> q;
	for (int i = 1; i <= n; ++i){
		for (int j: tr[i]) q.push(j);
		
		int cnt = r;
		while((cnt > 0) & !(q.empty())){
			cout << q.front() << " ";
			q.pop();
			--cnt;
		}
		cout << "0\n";
	}
}

int main(){	
	//int t; cin >> t;
	//while(t--)
	solve();
	
}
	

• Subtask 1: 100 / 100