oj.uz

Submission #532593

# Submission time Handle Problem Language Result Execution time Memory
532593 2022-03-03T09:39:29 Z GioChkhaidze Job Scheduling (CEOI12_jobs) C++17
100 / 100
 248 ms 16168 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=1e6+6;
int n,d,m;
pair < int , int > a[N];
bool check(int x) {
	int j=0,X=0;
	for (int Days=1; Days<=n; Days++) {
		X=x;
		while (j+1<=m && X-1>=0 && a[j+1].F<=Days) {
			if (Days>a[j+1].F+d) return 0;
			X--,j++;
		}
	}
	if (j!=m) return 0;
	return 1;
}
 
main () {
	scanf("%d%d%d",&n,&d,&m);
	
	for (int i=1; i<=m; i++) {
		scanf("%d",&a[i].F);
		a[i].S=i;
	}
	
	sort(a+1,a+m+1);
	
	int l=1,r=m,mid,res=-1;
	
	while (l<=r) {
		mid=(l+r)/2;
		if (check(mid)) r=mid-1,res=mid;
			else l=mid+1;
	}
	
	printf("%d\n",res);
	
	int j=0,X=0;
	for (int Days=1; Days<=n; Days++) {
		X=res;
		while (j+1<=m && X-1>=0 && a[j+1].F<=Days) {
			printf("%d ",a[j+1].S);
			X--,j++;
		}
		printf("0\n");
	}
}

Compilation message

jobs.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main () {
      | ^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d%d%d",&n,&d,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d",&a[i].F);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1968 KB Output is correct
2 Correct 18 ms 1976 KB Output is correct
3 Correct 18 ms 1896 KB Output is correct
4 Correct 18 ms 1972 KB Output is correct
5 Correct 18 ms 1860 KB Output is correct
6 Correct 18 ms 1924 KB Output is correct
7 Correct 18 ms 1924 KB Output is correct
8 Correct 19 ms 1896 KB Output is correct
9 Correct 34 ms 2032 KB Output is correct
10 Correct 28 ms 1988 KB Output is correct
11 Correct 26 ms 1948 KB Output is correct
12 Correct 59 ms 3856 KB Output is correct
13 Correct 82 ms 5788 KB Output is correct
14 Correct 111 ms 7964 KB Output is correct
15 Correct 130 ms 9416 KB Output is correct
16 Correct 167 ms 11924 KB Output is correct
17 Correct 206 ms 13612 KB Output is correct
18 Correct 222 ms 14600 KB Output is correct
19 Correct 248 ms 16168 KB Output is correct
20 Correct 195 ms 13548 KB Output is correct