oj.uz

Submission #930097

# Submission time Handle Problem Language Result Execution time Memory
930097 2024-02-18T13:18:20 Z ByeWorld Job Scheduling (CEOI12_jobs) C++14
55 / 100
 291 ms 20912 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; 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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4304 KB Output isn't correct
2 Incorrect 24 ms 4232 KB Output isn't correct
3 Incorrect 24 ms 4292 KB Output isn't correct
4 Incorrect 24 ms 4292 KB Output isn't correct
5 Incorrect 23 ms 4384 KB Output isn't correct
6 Incorrect 24 ms 4368 KB Output isn't correct
7 Incorrect 23 ms 4336 KB Output isn't correct
8 Incorrect 24 ms 4304 KB Output isn't correct
9 Correct 31 ms 4556 KB Output is correct
10 Correct 31 ms 4552 KB Output is correct
11 Correct 32 ms 4296 KB Output is correct
12 Correct 65 ms 6156 KB Output is correct
13 Correct 98 ms 8372 KB Output is correct
14 Correct 146 ms 11056 KB Output is correct
15 Incorrect 168 ms 11764 KB Output isn't correct
16 Correct 211 ms 15280 KB Output is correct
17 Correct 243 ms 18288 KB Output is correct
18 Correct 272 ms 19840 KB Output is correct
19 Correct 291 ms 20912 KB Output is correct
20 Correct 249 ms 17132 KB Output is correct