Submission #847121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
847121	2023-09-09T07:29:37 Z	airths	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	22788 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<pair<ll,ll>> pq;
		fl(i,1,n+1){
			for (auto x:val[i]){
				// cout<<x;
				pq.push({-x.first, x.second});
			}
			// cout<<'\n';
			if (pq.size() && -pq.top().first<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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	4428 KB	Output is correct
2	Correct	159 ms	4420 KB	Output is correct
3	Correct	161 ms	4420 KB	Output is correct
4	Correct	161 ms	4284 KB	Output is correct
5	Correct	185 ms	4444 KB	Output is correct
6	Correct	162 ms	4336 KB	Output is correct
7	Correct	161 ms	4416 KB	Output is correct
8	Correct	160 ms	4436 KB	Output is correct
9	Correct	152 ms	11164 KB	Output is correct
10	Correct	146 ms	11180 KB	Output is correct
11	Correct	74 ms	3060 KB	Output is correct
12	Correct	227 ms	5524 KB	Output is correct
13	Correct	283 ms	9616 KB	Output is correct
14	Correct	371 ms	12884 KB	Output is correct
15	Correct	405 ms	13136 KB	Output is correct
16	Correct	377 ms	16868 KB	Output is correct
17	Correct	544 ms	22788 KB	Output is correct
18	Execution timed out	1045 ms	17648 KB	Time limit exceeded
19	Execution timed out	1053 ms	22544 KB	Time limit exceeded
20	Correct	543 ms	22580 KB	Output is correct