Submission #532593

#	Time	Username	Problem	Language	Result	Execution time	Memory
532593		GioChkhaidze	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	248 ms	16168 KiB

jobs

#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 (stderr)

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 / 100