Submission #1168047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168047		akuyga	Job Scheduling (CEOI12_jobs)	C++20	30 / 100	261 ms	26736 KiB

jobs

#include "bits/stdc++.h"
using namespace std;
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
int main() {
	int N,D,M;
	int c=0;
	cin>>N>>D>>M;
	vector<int> A[N+1];
	for(int i=1; i<=M; i++) {
		int x;
		cin>>x;
		A[x].push_back(i);
	}
	vector<vector<int>> best(N+1);
	int l=1,r=N;
	int m=M;
	while(l<=r) {
		int mid=(l+r)/2;
		vector<vector<int>> temp(N+1);
		bool b=1;
		for(int i=1; i<=N && b; i++) {
			queue<int> Q;
			for(auto j:A[i])Q.push(j);
			for(int j=i; j<i+D&&!Q.empty(); j++)
				while(temp[j].size()<mid&&!Q.empty()) {
					temp[j].push_back(Q.front());
					Q.pop();
				}
			if(!Q.empty()) {
				b=0;
			}
		}
		if(b) {
			best=temp;
			m=min(m,mid);
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<m<<'\n';
	for(int i=1; i<=N; i++) {
		for(auto j:best[i])cout<<j<<' ';
		cout<<0<<'\n';
	}
}

• Subtask 1: 30 / 100