oj.uz

Submission #1097720

# Submission time Handle Problem Language Result Execution time Memory
1097720 2024-10-08T04:25:44 Z Nurislam Job Scheduling (CEOI12_jobs) C++17
0 / 100
 220 ms 13876 KB 
#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 = 1e15;
	while(l < r){
		ll md = (l+r)>>1;
		//cout << md << '\n';
		if(ok(md)){
			r = md;
		}else l = md+1;
	}
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1628 KB Output isn't correct
2 Incorrect 13 ms 1628 KB Output isn't correct
3 Incorrect 13 ms 1764 KB Output isn't correct
4 Incorrect 14 ms 1624 KB Output isn't correct
5 Incorrect 13 ms 1628 KB Output isn't correct
6 Incorrect 13 ms 1688 KB Output isn't correct
7 Incorrect 13 ms 1844 KB Output isn't correct
8 Incorrect 13 ms 1628 KB Output isn't correct
9 Incorrect 26 ms 2020 KB Expected EOLN
10 Incorrect 27 ms 1872 KB Expected EOLN
11 Incorrect 23 ms 1760 KB Expected EOLN
12 Incorrect 47 ms 3156 KB Expected EOLN
13 Incorrect 72 ms 4584 KB Expected EOLN
14 Incorrect 109 ms 6228 KB Expected EOLN
15 Incorrect 117 ms 7764 KB Expected EOLN
16 Incorrect 148 ms 9252 KB Expected EOLN
17 Incorrect 178 ms 10548 KB Expected EOLN
18 Incorrect 188 ms 12080 KB Expected EOLN
19 Incorrect 220 ms 13876 KB Expected EOLN
20 Incorrect 173 ms 10552 KB Expected EOLN