답안 #1097718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097718	2024-10-08T04:22:54 Z	Nurislam	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	399 ms	24336 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));
	
	vector<vector<int>> ans2;
	auto ok = [&](ll x) -> bool{
		vector<vector<int>> rans;
		ll 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;
	};
	
	ll l = 1, r = 1e15, ans = m;
	while(l <= r){
		ll 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 'll' {aka 'long long int'} [-Wsign-compare]
   67 |   while(rans.size() < n)rans.pb({});
      |         ~~~~~~~~~~~~^~~

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	1112 KB	Output isn't correct
2	Incorrect	8 ms	1112 KB	Output isn't correct
3	Incorrect	8 ms	1112 KB	Output isn't correct
4	Incorrect	10 ms	1116 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	8 ms	1116 KB	Output isn't correct
8	Incorrect	8 ms	1116 KB	Output isn't correct
9	Correct	127 ms	9984 KB	Output is correct
10	Correct	123 ms	9988 KB	Output is correct
11	Correct	45 ms	2608 KB	Output is correct
12	Incorrect	70 ms	5196 KB	Output isn't correct
13	Correct	103 ms	7508 KB	Output is correct
14	Incorrect	198 ms	10656 KB	Output isn't correct
15	Incorrect	164 ms	11788 KB	Output isn't correct
16	Correct	264 ms	15268 KB	Output is correct
17	Correct	314 ms	17776 KB	Output is correct
18	Correct	270 ms	20008 KB	Output is correct
19	Correct	399 ms	24336 KB	Output is correct
20	Correct	310 ms	17824 KB	Output is correct