답안 #1097708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097708	2024-10-08T03:29:34 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	260 ms	24144 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++;}
	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:67:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |   while(rans.size() < n)rans.pb({});
      |         ~~~~~~~~~~~~^~~

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	1116 KB	Output isn't correct
2	Incorrect	8 ms	1116 KB	Output isn't correct
3	Incorrect	10 ms	1116 KB	Output isn't correct
4	Incorrect	8 ms	1112 KB	Output isn't correct
5	Incorrect	8 ms	1116 KB	Output isn't correct
6	Incorrect	8 ms	1116 KB	Output isn't correct
7	Incorrect	9 ms	1112 KB	Output isn't correct
8	Incorrect	8 ms	1116 KB	Output isn't correct
9	Correct	52 ms	9872 KB	Output is correct
10	Correct	49 ms	9960 KB	Output is correct
11	Correct	26 ms	2640 KB	Output is correct
12	Incorrect	53 ms	5200 KB	Output isn't correct
13	Correct	76 ms	7504 KB	Output is correct
14	Incorrect	124 ms	10656 KB	Output isn't correct
15	Incorrect	125 ms	11856 KB	Output isn't correct
16	Correct	177 ms	15268 KB	Output is correct
17	Correct	203 ms	17792 KB	Output is correct
18	Correct	212 ms	20088 KB	Output is correct
19	Correct	260 ms	24144 KB	Output is correct
20	Correct	233 ms	18036 KB	Output is correct