Submission #1097698

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097698	2024-10-08T03:18:14 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	679 ms	27196 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

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	67 ms	2360 KB	Output isn't correct
2	Incorrect	61 ms	2380 KB	Output isn't correct
3	Incorrect	66 ms	2376 KB	Output isn't correct
4	Incorrect	61 ms	2364 KB	Output isn't correct
5	Incorrect	66 ms	2380 KB	Output isn't correct
6	Incorrect	100 ms	2352 KB	Output isn't correct
7	Incorrect	59 ms	2380 KB	Output isn't correct
8	Incorrect	59 ms	2380 KB	Output isn't correct
9	Correct	314 ms	10224 KB	Output is correct
10	Correct	318 ms	10336 KB	Output is correct
11	Correct	73 ms	3120 KB	Output is correct
12	Incorrect	128 ms	6736 KB	Extra information in the output file
13	Correct	232 ms	8532 KB	Output is correct
14	Incorrect	417 ms	14052 KB	Extra information in the output file
15	Incorrect	349 ms	15528 KB	Extra information in the output file
16	Correct	576 ms	17672 KB	Output is correct
17	Correct	643 ms	20836 KB	Output is correct
18	Correct	561 ms	22628 KB	Output is correct
19	Correct	679 ms	27196 KB	Output is correct
20	Correct	621 ms	20744 KB	Output is correct