oj.uz

Submission #743260

# Submission time Handle Problem Language Result Execution time Memory
743260 2023-05-17T09:16:47 Z NintsiChkhaidze Job Scheduling (CEOI12_jobs) C++17
100 / 100
 495 ms 26144 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
using namespace std;
 
const int N = 1e5 + 5;
pair <int,int> a[1000005];
vector <int> v[N],ans[N];
int n,m,d;
 
bool check(int x){
	int l = 1;
	for (int i = 1; i <= n; i++){
		v[i].clear();
		while (l <= m && a[l].f <= i && i - a[l].f <= d && v[i].size() < x){
			v[i].pb(a[l].s);
			++l;
		}
	}
	if (l != m + 1) return 0;
	
	for (int i = 1; i <= n; i++){
		ans[i] = v[i];
	}
	return 1; 
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    cin>>n>>d>>m;
    
	for (int i = 1; i <= m; i++){
		cin>>a[i].f;
		a[i].s = i;
	}
	sort(a+1,a+m+1);
	
	int l = 1, r = m,res=0;
	while (l <= r){
		int mid = (l + r)>>1;
		if (check(mid)){
			res=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<res<<endl;
	for (int i = 1; i <= n; i++){
		for (int x: v[i]) cout<<x<<" ";
		cout<<0<<endl;
	}
}
 
/*
8 2 12 
1 2 4 2 1 3 5 6 2 3 6 4 
*/

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:17:66: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |   while (l <= m && a[l].f <= i && i - a[l].f <= d && v[i].size() < x){
      |                                                      ~~~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7364 KB Output is correct
2 Correct 42 ms 7460 KB Output is correct
3 Correct 39 ms 7440 KB Output is correct
4 Correct 43 ms 7448 KB Output is correct
5 Correct 39 ms 7516 KB Output is correct
6 Correct 38 ms 7456 KB Output is correct
7 Correct 38 ms 7372 KB Output is correct
8 Correct 38 ms 7368 KB Output is correct
9 Correct 173 ms 7652 KB Output is correct
10 Correct 170 ms 7668 KB Output is correct
11 Correct 44 ms 7468 KB Output is correct
12 Correct 70 ms 10040 KB Output is correct
13 Correct 115 ms 12844 KB Output is correct
14 Correct 174 ms 15712 KB Output is correct
15 Correct 191 ms 17492 KB Output is correct
16 Correct 260 ms 20344 KB Output is correct
17 Correct 286 ms 24612 KB Output is correct
18 Correct 319 ms 24824 KB Output is correct
19 Correct 495 ms 26144 KB Output is correct
20 Correct 322 ms 24672 KB Output is correct