Submission #1097717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097717	2024-10-08T04:20:40 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	35 / 100	521 ms	42780 KB

jobs

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>  
using namespace std;
//using namespace __gnu_pbds;z
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
//#define ordst tree<pair<int,int>,  null_type,  less<pair<int,int>>,  rb_tree_tag ,  tree_order_statistics_node_update >
//#define double long double 
//template <class F, class _S>
//bool chmin(F &u, const _S &v){
	//bool flag = false;
	//if ( u > v ){
		//u = v; flag |= true;
	//}
	//return flag;
//}

//template <class F, class _S>
//bool chmax(F &u, const _S &v){
	//bool flag = false;
	//if ( u < v ){
		//u = v; flag |= true;
	//}
	//return flag;
//}

const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

void solve(){
	int n, d, m;
	cin >> n >> d >> m;
	vector<array<int,2>> v(m);
	int ii = 1;
	for(auto &[f, s]:v){cin >> f; s = ii++;}
	sort(all(v));
	
	vector<vector<int>> ans2;
	auto ok = [&](int x) -> bool{
		vector<vector<int>> rans;
		int cnt = x, day = 1, it = 0;
		while(day < n){
			bool ok = 1;
			vector<int> ad;
			cnt = x;
			while(cnt-- && it < m && v[it][0] <= day){
				if(v[it][0]+d < day)return false;
				ad.pb(v[it][1]);
				it++;
				ok = 0;
				//cout << it << '\n';
			}
			//cout << x << '\n';
			day++;
			rans.pb(ad);
			if(ok)break;
		}
		if(it < m)return false;
		while(rans.size() < n)rans.pb({});
		ans2 = rans;
		return true;
	};
	
	int l = 1, r = inf, ans = m;
	while(l <= r){
		int md = (l+r)>>1;
		//cout << md << '\n';
		if(ok(md)){
			ans = md;
			r = md-1;
		}else l = md+1;
	}
	//for(int i = r+100; i >= r-100; i--){
		//if(ok(i)){
			//ans = i;
		//}else break;
	//}
	ok(ans);
	cout << ans << '\n';
	for(auto i:ans2){
		for(auto j:i)cout << j << ' ';
		cout << "0\n";
	}
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}

Compilation message

jobs.cpp: In lambda function:
jobs.cpp:67:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |   while(rans.size() < n)rans.pb({});
      |         ~~~~~~~~~~~~^~~

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	2392 KB	Output isn't correct
2	Incorrect	8 ms	2140 KB	Output isn't correct
3	Incorrect	8 ms	2148 KB	Output isn't correct
4	Incorrect	11 ms	2136 KB	Output isn't correct
5	Incorrect	8 ms	2136 KB	Output isn't correct
6	Incorrect	9 ms	2392 KB	Output isn't correct
7	Incorrect	9 ms	2140 KB	Output isn't correct
8	Incorrect	9 ms	2140 KB	Output isn't correct
9	Correct	170 ms	11884 KB	Output is correct
10	Correct	180 ms	11856 KB	Output is correct
11	Correct	45 ms	4820 KB	Output is correct
12	Incorrect	96 ms	9044 KB	Output isn't correct
13	Correct	121 ms	13396 KB	Output is correct
14	Incorrect	237 ms	19208 KB	Output isn't correct
15	Incorrect	225 ms	21844 KB	Output isn't correct
16	Correct	329 ms	27896 KB	Output is correct
17	Correct	380 ms	32676 KB	Output is correct
18	Runtime error	345 ms	36528 KB	Memory limit exceeded
19	Runtime error	521 ms	42780 KB	Memory limit exceeded
20	Correct	367 ms	32676 KB	Output is correct