oj.uz

Submission #446570

# Submission time Handle Problem Language Result Execution time Memory
446570 2021-07-22T13:05:12 Z ArianKheirandish Job Scheduling (CEOI12_jobs) C++17
25 / 100
 1000 ms 29040 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 = 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';
                
            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 170 ms 4876 KB Extra information in the output file
2 Incorrect 165 ms 4816 KB Extra information in the output file
3 Incorrect 252 ms 6848 KB Extra information in the output file
4 Incorrect 331 ms 8900 KB Extra information in the output file
5 Incorrect 408 ms 10920 KB Extra information in the output file
6 Incorrect 519 ms 12992 KB Extra information in the output file
7 Incorrect 576 ms 14916 KB Extra information in the output file
8 Incorrect 644 ms 16940 KB Extra information in the output file
9 Correct 39 ms 1860 KB Output is correct
10 Correct 38 ms 1856 KB Output is correct
11 Execution timed out 1090 ms 27368 KB Time limit exceeded
12 Correct 65 ms 3140 KB Output is correct
13 Execution timed out 1095 ms 28228 KB Time limit exceeded
14 Correct 131 ms 6052 KB Output is correct
15 Execution timed out 1090 ms 28452 KB Time limit exceeded
16 Execution timed out 1062 ms 27264 KB Time limit exceeded
17 Execution timed out 1096 ms 29040 KB Time limit exceeded
18 Correct 259 ms 11976 KB Output is correct
19 Execution timed out 1085 ms 28964 KB Time limit exceeded
20 Execution timed out 1091 ms 28968 KB Time limit exceeded