Submission #1097721

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097721	2024-10-08T04:27:32 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	207 ms	13888 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)
typedef long long ll;
void solve(){
	ll 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));
	
	auto ok = [&](ll x) -> bool{
		ll cnt = x, day = 1, it = 0;
		while(day <= n){
			bool ok = 1;
			cnt = x;
			while(cnt-- && it < m && v[it][0] <= day){
				if(v[it][0]+d < day)return false;
				it++;
				ok = 0;
			}
			day++;
			if(ok)break;
		}
		if(it < m)return false;
		return true;
	};
	
	ll l = 1, r = m;
	while(l < r){
		ll md = (l+r)>>1;
		//cout << md << '\n';
		if(ok(md)){
			r = md;
		}else l = md+1;
	}
	cout << l << '\n';
	ll cnt = l, day = 1, it = 0;
	while(day <= n){
		cnt = l;
		while(cnt-- && it < m && v[it][0] <= day){
			cout << v[it][1] << ' ';
			it++;
		}
		day++;
		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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	1628 KB	Output isn't correct
2	Incorrect	13 ms	1624 KB	Output isn't correct
3	Incorrect	13 ms	1624 KB	Output isn't correct
4	Incorrect	13 ms	1628 KB	Output isn't correct
5	Incorrect	13 ms	1628 KB	Output isn't correct
6	Incorrect	13 ms	1628 KB	Output isn't correct
7	Incorrect	14 ms	1628 KB	Output isn't correct
8	Incorrect	13 ms	1628 KB	Output isn't correct
9	Correct	24 ms	1884 KB	Output is correct
10	Correct	33 ms	1884 KB	Output is correct
11	Correct	20 ms	1628 KB	Output is correct
12	Correct	46 ms	3308 KB	Output is correct
13	Correct	61 ms	4688 KB	Output is correct
14	Correct	85 ms	6224 KB	Output is correct
15	Correct	107 ms	7704 KB	Output is correct
16	Correct	131 ms	9044 KB	Output is correct
17	Correct	151 ms	10580 KB	Output is correct
18	Correct	176 ms	12088 KB	Output is correct
19	Correct	207 ms	13888 KB	Output is correct
20	Correct	152 ms	10836 KB	Output is correct