oj.uz

Submission #66300

# Submission time Handle Problem Language Result Execution time Memory
66300 2018-08-10T07:44:55 Z ikura355 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 376 ms 13860 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]
  scanf("%d%d%d",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:26:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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 30 ms 1656 KB Output is correct
2 Correct 28 ms 1780 KB Output is correct
3 Correct 28 ms 1832 KB Output is correct
4 Correct 27 ms 1832 KB Output is correct
5 Correct 29 ms 1832 KB Output is correct
6 Correct 27 ms 1924 KB Output is correct
7 Correct 55 ms 1924 KB Output is correct
8 Correct 30 ms 2020 KB Output is correct
9 Correct 51 ms 2276 KB Output is correct
10 Correct 42 ms 2276 KB Output is correct
11 Correct 45 ms 2276 KB Output is correct
12 Correct 87 ms 3584 KB Output is correct
13 Correct 114 ms 5020 KB Output is correct
14 Correct 173 ms 6564 KB Output is correct
15 Correct 177 ms 7852 KB Output is correct
16 Correct 253 ms 9516 KB Output is correct
17 Correct 290 ms 10796 KB Output is correct
18 Correct 376 ms 12364 KB Output is correct
19 Correct 369 ms 13860 KB Output is correct
20 Correct 280 ms 13860 KB Output is correct