oj.uz

Submission #390204

# Submission time Handle Problem Language Result Execution time Memory
390204 2021-04-15T14:49:41 Z grobar Job Scheduling (CEOI12_jobs) C++14
100 / 100
 331 ms 13636 KB 
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 1e6 + 5;

int n,d,m;
pii a[maxn];

bool check(int num) {
    int cur = 0;
	for(int day=0;day<n;day++) {
        for(int i=0;i<num;i++) {
            if(cur<m && a[cur].X<=day+1 && a[cur].X+d>=day+1) cur++;
            else break;
        }
	}
    return cur==m;
}

int main() {
	scanf("%d%d%d",&n,&d,&m);
	for(int i=0;i<m;i++) scanf("%d",&a[i].X), a[i].Y = i+1;
	sort(&a[0],&a[m]);
	int l = 0, r = m, mid, res = -1;
	while(l<=r) {
		mid = (l+r)/2;
		if(check(mid)) {
			res = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	printf("%d\n",res);
    int cur = 0;
	for(int day=0;day<n;day++) {
        for(int i=0;i<res;i++) {
            if(cur<m && a[cur].X<=day+1 && a[cur].X+d>=day+1) {
                printf("%d ",a[cur].Y);
                cur++;
            }
            else break;
        }
        printf("0\n");
	}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d%d%d",&n,&d,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:26:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  for(int i=0;i<m;i++) scanf("%d",&a[i].X), a[i].Y = i+1;
      |                       ~~~~~^~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1600 KB Output is correct
2 Correct 26 ms 1596 KB Output is correct
3 Correct 34 ms 1604 KB Output is correct
4 Correct 27 ms 1568 KB Output is correct
5 Correct 27 ms 1612 KB Output is correct
6 Correct 26 ms 1724 KB Output is correct
7 Correct 26 ms 1688 KB Output is correct
8 Correct 26 ms 1624 KB Output is correct
9 Correct 40 ms 1776 KB Output is correct
10 Correct 40 ms 1828 KB Output is correct
11 Correct 34 ms 1596 KB Output is correct
12 Correct 70 ms 3128 KB Output is correct
13 Correct 106 ms 4548 KB Output is correct
14 Correct 147 ms 6036 KB Output is correct
15 Correct 182 ms 7660 KB Output is correct
16 Correct 220 ms 9028 KB Output is correct
17 Correct 261 ms 10620 KB Output is correct
18 Correct 298 ms 11956 KB Output is correct
19 Correct 331 ms 13636 KB Output is correct
20 Correct 259 ms 10564 KB Output is correct