oj.uz

Submission #930099

# Submission time Handle Problem Language Result Execution time Memory
930099 2024-02-18T13:21:37 Z ByeWorld Job Scheduling (CEOI12_jobs) C++14
0 / 100
 1000 ms 65536 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1337 ms 65536 KB Time limit exceeded
2 Execution timed out 2786 ms 65536 KB Time limit exceeded
3 Execution timed out 2870 ms 65536 KB Time limit exceeded
4 Execution timed out 2851 ms 65536 KB Time limit exceeded
5 Execution timed out 2810 ms 65536 KB Time limit exceeded
6 Execution timed out 2831 ms 65536 KB Time limit exceeded
7 Execution timed out 2846 ms 65536 KB Time limit exceeded
8 Execution timed out 2715 ms 65536 KB Time limit exceeded
9 Incorrect 40 ms 9980 KB Output isn't correct
10 Incorrect 40 ms 9716 KB Output isn't correct
11 Execution timed out 2888 ms 65536 KB Time limit exceeded
12 Execution timed out 2806 ms 65536 KB Time limit exceeded
13 Execution timed out 2811 ms 65536 KB Time limit exceeded
14 Execution timed out 2785 ms 65536 KB Time limit exceeded
15 Runtime error 617 ms 65536 KB Execution killed with signal 9
16 Runtime error 558 ms 65536 KB Execution killed with signal 9
17 Runtime error 568 ms 65536 KB Execution killed with signal 9
18 Runtime error 473 ms 65536 KB Execution killed with signal 9
19 Runtime error 340 ms 65536 KB Execution killed with signal 9
20 Execution timed out 2578 ms 65536 KB Time limit exceeded