oj.uz

Submission #930103

# Submission time Handle Problem Language Result Execution time Memory
930103 2024-02-18T13:29:39 Z ByeWorld Job Scheduling (CEOI12_jobs) C++14
100 / 100
 302 ms 21392 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
//#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int INF = 1e9+10;
const int MAXN = 1e6+10;

int a[MAXN];
vector <pii> vec;
vector <vector<int>> ans;
int n, d, k, num;

bool cek(int x){ // number of machine
	int cnt = 1;
	for(int i=0; i<n; ){
		int las = i;
		for(int j=0; j<x && las<n; j++){
			if(cnt < vec[las].fi) break;
			if(cnt-vec[las].fi > d) return 0;
			las++;
		}
		i = las;
		cnt++;
	}

	return 1;
}
void bin(){
	int l=1, r=n, mid=-1, cnt=-1;
	while(l<=r){
		mid = md;
		if(cek(mid)){
			r = mid-1; cnt = mid;
		} else l = mid+1;
	}
	num = cnt;
}
signed main() {
	cin >> k >> d >> n;
	for(int i=1; i<=n; i++){
		cin >> a[i]; vec.pb({a[i], i});
	}
	sort(vec.begin(), vec.end());

	bin();

	int cnt = 1;
	for(int i=0; i<n; ){
		vector <int> te;
		int las = i;
		for(int j=0; j<num && las<n; j++){
			if(cnt < vec[las].fi) break;
			te.pb(vec[las].se);
			las++;
		}
		i = las;
		cnt++;

		ans.pb(te);
	}

	cout << num << '\n';
	for(auto vec : ans){
		for(auto in : vec){
			cout << in << ' '; 
		}
		cout << "0\n";
	}
	for(int i=0; i<k-ans.size(); i++) cout << "0\n";
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i=0; i<k-ans.size(); i++) cout << "0\n";
      |               ~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4680 KB Output is correct
2 Correct 24 ms 4560 KB Output is correct
3 Correct 25 ms 4552 KB Output is correct
4 Correct 25 ms 4560 KB Output is correct
5 Correct 25 ms 4548 KB Output is correct
6 Correct 25 ms 4560 KB Output is correct
7 Correct 25 ms 4608 KB Output is correct
8 Correct 24 ms 4560 KB Output is correct
9 Correct 32 ms 4624 KB Output is correct
10 Correct 32 ms 4604 KB Output is correct
11 Correct 32 ms 4296 KB Output is correct
12 Correct 66 ms 6144 KB Output is correct
13 Correct 98 ms 9400 KB Output is correct
14 Correct 144 ms 10224 KB Output is correct
15 Correct 169 ms 11880 KB Output is correct
16 Correct 215 ms 14812 KB Output is correct
17 Correct 254 ms 18096 KB Output is correct
18 Correct 264 ms 18604 KB Output is correct
19 Correct 302 ms 21392 KB Output is correct
20 Correct 253 ms 17072 KB Output is correct