oj.uz

Submission #930100

# Submission time Handle Problem Language Result Execution time Memory
930100 2024-02-18T13:22:27 Z ByeWorld Job Scheduling (CEOI12_jobs) C++14
55 / 100
 286 ms 21676 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) break;
			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:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  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 23 ms 4304 KB Output isn't correct
2 Incorrect 23 ms 4396 KB Output isn't correct
3 Incorrect 22 ms 4304 KB Output isn't correct
4 Incorrect 26 ms 4304 KB Output isn't correct
5 Incorrect 27 ms 4292 KB Output isn't correct
6 Incorrect 24 ms 4288 KB Output isn't correct
7 Incorrect 23 ms 4304 KB Output isn't correct
8 Incorrect 23 ms 4304 KB Output isn't correct
9 Correct 31 ms 4548 KB Output is correct
10 Correct 31 ms 4552 KB Output is correct
11 Correct 32 ms 4348 KB Output is correct
12 Correct 63 ms 6340 KB Output is correct
13 Correct 94 ms 8960 KB Output is correct
14 Correct 137 ms 10680 KB Output is correct
15 Incorrect 158 ms 11960 KB Output isn't correct
16 Correct 231 ms 14820 KB Output is correct
17 Correct 250 ms 16948 KB Output is correct
18 Correct 254 ms 18860 KB Output is correct
19 Correct 286 ms 21676 KB Output is correct
20 Correct 242 ms 17072 KB Output is correct