Submission #1097693

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097693	2024-10-08T03:14:55 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	405 ms	42792 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++;}
	//for(auto [i, j]:v)cout << i << ' ';
	//cout << '\n';
	//for(auto [i, j]:v)cout << j << ' ';
	//cout << '\n';
	sort(all(v));
	vector<vector<int>> ans2;
	auto ok = [&](int x) -> bool{
		vector<vector<int>> rans;
		int cnt = x, day = 1, it = 0;
		while(true){
			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;
		}
		while((int)rans.size() < n)rans.pb({});
		ans2 = rans;
		return true;
	};
	
	int l = 1, r = m, 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;
	}
	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();
	}
}

Subtask #1

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	3136 KB	Output isn't correct
2	Incorrect	19 ms	3136 KB	Output isn't correct
3	Incorrect	18 ms	3164 KB	Output isn't correct
4	Incorrect	18 ms	3148 KB	Output isn't correct
5	Incorrect	18 ms	3164 KB	Output isn't correct
6	Incorrect	18 ms	3148 KB	Output isn't correct
7	Incorrect	18 ms	3156 KB	Output isn't correct
8	Incorrect	18 ms	3152 KB	Output isn't correct
9	Correct	68 ms	11772 KB	Output is correct
10	Correct	60 ms	11824 KB	Output is correct
11	Correct	35 ms	4944 KB	Output is correct
12	Incorrect	69 ms	10572 KB	Extra information in the output file
13	Correct	102 ms	13424 KB	Output is correct
14	Incorrect	170 ms	22452 KB	Extra information in the output file
15	Incorrect	174 ms	25384 KB	Extra information in the output file
16	Correct	262 ms	27804 KB	Output is correct
17	Runtime error	278 ms	32928 KB	Memory limit exceeded
18	Runtime error	310 ms	36436 KB	Memory limit exceeded
19	Runtime error	405 ms	42792 KB	Memory limit exceeded
20	Runtime error	320 ms	32932 KB	Memory limit exceeded