oj.uz

Submission #930096

# Submission time Handle Problem Language Result Execution time Memory
930096 2024-02-18T13:13:38 Z ByeWorld Job Scheduling (CEOI12_jobs) C++14
15 / 100
 300 ms 23736 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 = 0;
	for(int i=0; i<n; i+=x){
		for(int j=0; j<x && i+j<n; j++){
			if(cnt-vec[i+j].fi > d) return 0;
		}
		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();

	for(int i=0; i<n; i+=num){
		vector <int> te;
		for(int j=0; j<num && i+j<n; j++){
			te.pb(vec[i+j].se);
		}
		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:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0; i<k-ans.size(); i++) cout << "0\n";
      |               ~^~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 4716 KB Output isn't correct
2 Incorrect 40 ms 4768 KB Output isn't correct
3 Incorrect 23 ms 4524 KB Output isn't correct
4 Incorrect 24 ms 4512 KB Output isn't correct
5 Incorrect 34 ms 4548 KB Output isn't correct
6 Incorrect 23 ms 4556 KB Output isn't correct
7 Incorrect 24 ms 4556 KB Output isn't correct
8 Incorrect 35 ms 4560 KB Output isn't correct
9 Incorrect 30 ms 4556 KB Output isn't correct
10 Incorrect 30 ms 4552 KB Output isn't correct
11 Incorrect 32 ms 4724 KB Output isn't correct
12 Correct 65 ms 7104 KB Output is correct
13 Incorrect 100 ms 9488 KB Output isn't correct
14 Correct 141 ms 10932 KB Output is correct
15 Incorrect 160 ms 12728 KB Output isn't correct
16 Correct 211 ms 17928 KB Output is correct
17 Incorrect 250 ms 16952 KB Output isn't correct
18 Incorrect 300 ms 22192 KB Output isn't correct
19 Incorrect 295 ms 23736 KB Output isn't correct
20 Incorrect 247 ms 17836 KB Output isn't correct