oj.uz

답안 #446573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446573 2021-07-22T13:13:13 Z ArianKheirandish Job Scheduling (CEOI12_jobs) C++17
100 / 100
 313 ms 13676 KB 
//in the name of god//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)		x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair

const int maxn = 1e6 + 10;
const int LG = 30;
const ll Inf = 1e9;
int n, d, m;
vector < pair<int, int> > a;

bool check(int x){
	int now = 1;
	int z = 0;
	for(int i = 0 ; i < m ; i ++){
		if(a[i].F > now)
			now = a[i].F,
			z = 1;
		
		else if(a[i].F < now - d)
			return 0;
			
		else if(a[i].F >= now - d)
			z ++;
		
		if(z >= x)
			z = 0,
			now ++;
	}
	return 1;
}

int main(){_
	cin >> n >> d >> m;	
	a.resize(m);
	for(int i = 0; i < m ; i ++){
		cin >> a[i].F;
		a[i].S = i + 1;
	}
	
	sort(all(a));
	
	int l = 1, r = m;
	while(l < r){
		int mid = (l + r) / 2; 
		if(check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	
	cout << r << '\n';
	int now = 1;
	int z = 0;
	for(int i = 0; i < m ; i ++){
        if(a[i].F > now){
            for (int j = now ; j < a[i].F; j ++)
                cout << 0 << '\n';
                
            now = a[i].F;
            z = 1;
        }
        
        else if(a[i].F >= now - d){
            cout << a[i].S << " ";
            z ++;
        }
        
        if(z >= r){
            cout << 0 << '\n';
            z = 0;
            now ++;
        }
    }
    
    for (int i = now ; i <= n ; i ++)
        cout << 0 << '\n';
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1604 KB Output is correct
2 Correct 25 ms 1620 KB Output is correct
3 Correct 24 ms 1692 KB Output is correct
4 Correct 24 ms 1652 KB Output is correct
5 Correct 24 ms 1612 KB Output is correct
6 Correct 24 ms 1612 KB Output is correct
7 Correct 26 ms 1620 KB Output is correct
8 Correct 24 ms 1708 KB Output is correct
9 Correct 41 ms 1864 KB Output is correct
10 Correct 40 ms 1868 KB Output is correct
11 Correct 32 ms 1668 KB Output is correct
12 Correct 66 ms 3144 KB Output is correct
13 Correct 102 ms 4548 KB Output is correct
14 Correct 136 ms 6140 KB Output is correct
15 Correct 165 ms 7564 KB Output is correct
16 Correct 204 ms 9104 KB Output is correct
17 Correct 243 ms 10564 KB Output is correct
18 Correct 269 ms 12100 KB Output is correct
19 Correct 313 ms 13676 KB Output is correct
20 Correct 242 ms 10832 KB Output is correct