Submission #54495

#	Time	Username	Problem	Language	Result	Execution time	Memory
54495		Bruteforceman	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	428 ms	24348 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
vector <int> g[100010];
int n, m, d;
int a[1000010];

bool good(int x) {
	queue <int> Q;
	for(int i = 1; i <= n; i++) {
		for(auto j : g[i]) {
			Q.push(j);
		}
		for(int j = 0; j < x && !Q.empty(); j++) {
			int u = Q.front();
			Q.pop();
			if(i - a[u] > d) return false;
		}
	}
	return Q.empty();
}
void print(int x) {
	printf("%d\n", x);
	queue <int> Q;
	for(int i = 1; i <= n; i++) {
		for(auto j : g[i]) {
			Q.push(j);
		}
		for(int j = 0; j < x && !Q.empty(); j++) {
			int u = Q.front();
			Q.pop();
			printf("%d ", u);
		}
		printf("0\n");
	}
	return ;
}

int search(int b, int e) {
	if(b == e) {
		return b;
	} 
	int m = (b + e) >> 1;
	if(good(m)) return search(b, m);
	else return search(m + 1, e);
}

int main (int argc, char const* argv[])
{
	scanf("%d %d %d", &n, &d, &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
		g[a[i]].push_back(i);
	}
	print(search(0, m));
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main(int, const char**)':
jobs.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100