Submission #847122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
847122	2023-09-09T07:30:47 Z	airths	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	553 ms	30092 KB

jobs

/*
 * 
 * 	^v^
 * 
 */
#include <iostream>
#include <numeric>
#include <set>
#include <iomanip>
#include <chrono>
#include <queue>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <bitset>
#include <algorithm>
#include <array>
#include <random>

using namespace std;

using ll = int;
using ld = long double;

#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define fl(i,a,n) for (ll i(a); i<n; i++)
#define rfl(i,a,n) for (ll i(n-1); i>=a; i--)
#define ty int _; for(cin>>_; _--;)
#define print(a) for(auto ele:a){cout<<ele<<" ";}cout<<'\n';

template <typename L, typename R>
inline bool chmax(L &a, R &b){if (a<b){a=b;return 1;}return 0;}
template <typename L, typename R>
inline bool chmin(L &a, R &b){if (a>b){a=b;return 1;}return 0;}

template <typename L, typename R>
ostream& operator<<(ostream &fout, const pair<L, R> &p){
	fout<<"{"<<p.first<<","<<p.second<<"}";
	return fout;
}

template <typename T>
ostream& operator<<(ostream &fout, const vector <T> &v){
	for (auto &x:v){
		fout<<x<<" ";
	}
	fout<<"\n";
	return fout;
}

template <typename T>
ostream& operator<<(ostream &fout, const set <T> &st){
	for (auto &x:st){
		fout<<x<<" ";
	}
	fout<<"\n";
	return fout;
}

template <typename K, typename V>
ostream& operator<<(ostream &fout, const map<K, V> &mp){
	fout<<"[";
	for (auto &[x,y]:mp){
		fout<<x<<":"<<y<<" ";
	}
	fout<<"]\n";
	return fout;
}

ll gcd(ll a, ll b){
	if (b==0){
		return a;
	}
	return gcd(b, a%b);
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll pw(ll a, ll b, ll m){
	ll res=1;
	a%=m;
	while (b){
		if (b&1){
			res=(res*a)%m;
		}
		a=(a*a)%m;
		b/=2;
	}
	return res;
}

void scn(){
	ll n, d, m; cin>>n>>d>>m;
	vector <ll> a(m);
	fl(i,0,m){
		cin>>a[i];
	}
	vector <vector <pair<ll,ll>>> val(n+1);
	fl(i,0,m){
		val[a[i]].push_back({a[i]+d, i+1});
	}
	auto bin=[&](ll mid){
		priority_queue<ll> pq;
		fl(i,1,n+1){
			for (auto &x:val[i]){
				// cout<<x;
				pq.push(-x.first);
			}
			// cout<<'\n';
			if (pq.size() && -pq.top()<i){
				return false;
			}
			ll cur = mid;
			while (cur-- && pq.size()){
				pq.pop();
			}
		}
		return true;
	};
	// cout<<bin(1)<<" "<<bin(2)<<'\n';
	ll l = 1, r = m+1;
	while (l<=r){
		ll mid = (l+r)/2;
		if (bin(mid)){
			r = mid-1;
		} else {
			l = mid+1;
		}
	}
	cout<<l<<'\n';
	priority_queue<pair<ll,ll>> pq;
	vector <vector <ll>> ans(n+1);
	fl(i,1,n+1){
		for (auto x:val[i]){
			pq.push({-x.first, x.second});
		}
		ll cur = l;
		while (cur-- && pq.size()){
			ans[i].push_back(pq.top().second);
			pq.pop();
		}
		ans[i].push_back(0);
	}
	fl(i,1,n+1){
		fl(j,0,ans[i].size()){
			cout<<ans[i][j]<<" \n"[j==(ans[i].size()-1)];
		}
	}

	// not necessarily distinct
	// right down
}

int main(){
	iamtefu;
#if defined(airths)
	auto t1=chrono::high_resolution_clock::now();
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	// ty
	{
		scn();
	}
#if defined(airths)
	auto t2=chrono::high_resolution_clock::now();
	ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
	ti*=1e-6;
	cerr<<"Time: "<<setprecision(12)<<ti;
	cerr<<"ms\n";
#endif
	return 0;
}

Compilation message

jobs.cpp: In function 'void scn()':
jobs.cpp:27:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | #define fl(i,a,n) for (ll i(a); i<n; i++)
......
  146 |   fl(j,0,ans[i].size()){
      |      ~~~~~~~~~~~~~~~~~            
jobs.cpp:146:3: note: in expansion of macro 'fl'
  146 |   fl(j,0,ans[i].size()){
      |   ^~
jobs.cpp:147:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    cout<<ans[i][j]<<" \n"[j==(ans[i].size()-1)];
      |                           ~^~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	4036 KB	Output is correct
2	Correct	55 ms	4248 KB	Output is correct
3	Correct	52 ms	4036 KB	Output is correct
4	Correct	55 ms	4036 KB	Output is correct
5	Correct	54 ms	4120 KB	Output is correct
6	Correct	55 ms	4240 KB	Output is correct
7	Correct	52 ms	4132 KB	Output is correct
8	Correct	55 ms	4076 KB	Output is correct
9	Correct	69 ms	10828 KB	Output is correct
10	Correct	78 ms	11132 KB	Output is correct
11	Correct	36 ms	2896 KB	Output is correct
12	Correct	149 ms	5556 KB	Output is correct
13	Correct	156 ms	9808 KB	Output is correct
14	Correct	238 ms	12712 KB	Output is correct
15	Correct	176 ms	13084 KB	Output is correct
16	Correct	188 ms	16980 KB	Output is correct
17	Correct	313 ms	22608 KB	Output is correct
18	Correct	553 ms	22096 KB	Output is correct
19	Correct	520 ms	30092 KB	Output is correct
20	Correct	306 ms	22560 KB	Output is correct