oj.uz

Submission #847115

# Submission time Handle Problem Language Result Execution time Memory
847115 2023-09-09T07:25:24 Z airths Job Scheduling (CEOI12_jobs) C++17
60 / 100
 1000 ms 22820 KB 
/*
 * 
 * 	^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);
		}
		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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 4416 KB Output is correct
2 Correct 158 ms 4424 KB Output is correct
3 Correct 158 ms 4536 KB Output is correct
4 Correct 162 ms 4416 KB Output is correct
5 Correct 159 ms 4380 KB Output is correct
6 Correct 158 ms 4368 KB Output is correct
7 Correct 158 ms 4424 KB Output is correct
8 Correct 158 ms 4412 KB Output is correct
9 Partially correct 146 ms 11004 KB Partially correct
10 Partially correct 145 ms 11148 KB Partially correct
11 Partially correct 70 ms 3172 KB Partially correct
12 Partially correct 221 ms 5532 KB Partially correct
13 Partially correct 280 ms 9936 KB Partially correct
14 Partially correct 345 ms 12884 KB Partially correct
15 Partially correct 393 ms 13136 KB Partially correct
16 Partially correct 334 ms 16976 KB Partially correct
17 Partially correct 529 ms 22768 KB Partially correct
18 Execution timed out 1036 ms 20392 KB Time limit exceeded
19 Execution timed out 1042 ms 20096 KB Time limit exceeded
20 Partially correct 535 ms 22820 KB Partially correct