답안 #1097706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097706	2024-10-08T03:21:13 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	655 ms	26596 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(day < n){
			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;
		}
		if(it < m)return false;
		while(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();
	}
}

Compilation message

jobs.cpp: In lambda function:
jobs.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   while(rans.size() < n)rans.pb({});
      |         ~~~~~~~~~~~~^~~

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	1372 KB	Output isn't correct
2	Incorrect	22 ms	1472 KB	Output isn't correct
3	Incorrect	15 ms	1520 KB	Output isn't correct
4	Incorrect	15 ms	1372 KB	Output isn't correct
5	Incorrect	14 ms	1372 KB	Output isn't correct
6	Incorrect	14 ms	1524 KB	Output isn't correct
7	Incorrect	18 ms	1368 KB	Output isn't correct
8	Incorrect	15 ms	1524 KB	Output isn't correct
9	Correct	326 ms	10228 KB	Output is correct
10	Correct	290 ms	10308 KB	Output is correct
11	Correct	73 ms	3152 KB	Output is correct
12	Incorrect	134 ms	5720 KB	Output isn't correct
13	Correct	195 ms	8272 KB	Output is correct
14	Incorrect	400 ms	12236 KB	Output isn't correct
15	Incorrect	304 ms	13140 KB	Output isn't correct
16	Correct	538 ms	17072 KB	Output is correct
17	Correct	639 ms	20260 KB	Output is correct
18	Correct	516 ms	21804 KB	Output is correct
19	Correct	655 ms	26596 KB	Output is correct
20	Correct	614 ms	19988 KB	Output is correct