oj.uz

답안 #1097721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097721 2024-10-08T04:27:32 Z Nurislam Job Scheduling (CEOI12_jobs) C++17
60 / 100
 207 ms 13888 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 = 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

# 결과 실행 시간 메모리 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