Submission #54494

# Submission time Handle Problem Language Result Execution time Memory
54494 2018-07-03T17:08:24 Z Bruteforceman Job Scheduling (CEOI12_jobs) C++11
45 / 100
405 ms 33792 KB
#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, n));
	return 0;
}

Compilation message

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]);
   ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 4764 KB Output isn't correct
2 Incorrect 34 ms 5272 KB Output isn't correct
3 Incorrect 29 ms 5444 KB Output isn't correct
4 Incorrect 30 ms 5988 KB Output isn't correct
5 Incorrect 28 ms 6204 KB Output isn't correct
6 Incorrect 29 ms 6456 KB Output isn't correct
7 Incorrect 30 ms 6888 KB Output isn't correct
8 Incorrect 29 ms 7156 KB Output isn't correct
9 Correct 39 ms 7360 KB Output is correct
10 Correct 39 ms 7652 KB Output is correct
11 Correct 34 ms 7816 KB Output is correct
12 Correct 63 ms 10120 KB Output is correct
13 Correct 93 ms 13568 KB Output is correct
14 Correct 188 ms 17120 KB Output is correct
15 Correct 193 ms 20260 KB Output is correct
16 Correct 237 ms 25252 KB Output is correct
17 Correct 298 ms 30952 KB Output is correct
18 Runtime error 291 ms 33792 KB Memory limit exceeded
19 Runtime error 405 ms 33792 KB Memory limit exceeded
20 Runtime error 289 ms 33792 KB Memory limit exceeded