oj.uz

Submission #446569

# Submission time Handle Problem Language Result Execution time Memory
446569 2021-07-22T13:04:05 Z ArianKheirandish Job Scheduling (CEOI12_jobs) C++14
25 / 100
 1000 ms 29328 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;
pair<int, int> a[maxn];

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;	
	for(int i = 0; i < m ; i ++){
		cin >> a[i].F;
		a[i].S = i + 1;
	}
	
	sort(a, a + m);
	
	int l = 0, r = m;
	while(l < r - 1){
		int mid = (l + r) / 2; 
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	
	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';
                
            n = 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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 5088 KB Extra information in the output file
2 Incorrect 173 ms 5176 KB Extra information in the output file
3 Incorrect 259 ms 7148 KB Extra information in the output file
4 Incorrect 332 ms 9212 KB Extra information in the output file
5 Incorrect 414 ms 11216 KB Extra information in the output file
6 Incorrect 521 ms 13224 KB Extra information in the output file
7 Incorrect 589 ms 15232 KB Extra information in the output file
8 Incorrect 667 ms 17228 KB Extra information in the output file
9 Correct 39 ms 2124 KB Output is correct
10 Correct 38 ms 2048 KB Output is correct
11 Execution timed out 1096 ms 27500 KB Time limit exceeded
12 Correct 68 ms 3780 KB Output is correct
13 Execution timed out 1097 ms 28492 KB Time limit exceeded
14 Correct 138 ms 6776 KB Output is correct
15 Execution timed out 1087 ms 27952 KB Time limit exceeded
16 Execution timed out 1070 ms 28524 KB Time limit exceeded
17 Execution timed out 1093 ms 28484 KB Time limit exceeded
18 Correct 262 ms 12652 KB Output is correct
19 Execution timed out 1095 ms 27828 KB Time limit exceeded
20 Execution timed out 1097 ms 29328 KB Time limit exceeded