Submission #1097696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097696	2024-10-08T03:17:23 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	802 ms	42904 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;
	}
	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();
	}
}

Subtask #1

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	70 ms	3148 KB	Output isn't correct
2	Incorrect	59 ms	3988 KB	Output isn't correct
3	Incorrect	59 ms	3164 KB	Output isn't correct
4	Incorrect	59 ms	3160 KB	Output isn't correct
5	Incorrect	59 ms	3152 KB	Output isn't correct
6	Incorrect	69 ms	3156 KB	Output isn't correct
7	Incorrect	59 ms	3144 KB	Output isn't correct
8	Incorrect	59 ms	3164 KB	Output isn't correct
9	Correct	366 ms	11868 KB	Output is correct
10	Correct	348 ms	11908 KB	Output is correct
11	Correct	80 ms	4944 KB	Output is correct
12	Incorrect	143 ms	10720 KB	Extra information in the output file
13	Correct	230 ms	13652 KB	Output is correct
14	Incorrect	508 ms	22452 KB	Extra information in the output file
15	Incorrect	371 ms	25404 KB	Extra information in the output file
16	Correct	590 ms	27796 KB	Output is correct
17	Runtime error	686 ms	33024 KB	Memory limit exceeded
18	Runtime error	568 ms	36624 KB	Memory limit exceeded
19	Runtime error	802 ms	42904 KB	Memory limit exceeded
20	Runtime error	650 ms	32836 KB	Memory limit exceeded