Submission #847109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
847109	2023-09-09T07:18:52 Z	airths	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1000 ms	32644 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({i+d, i+1});
	}
	auto bin=[&](ll mid){
		priority_queue<pair<ll,ll>> pq;
		fl(i,1,n+1){
			for (auto x:val[i]){
				pq.push(x);
			}
			if (pq.size() && pq.top().first<i){
				return false;
			}
			ll cur = mid;
			while (cur-- && pq.size()){
				pq.pop();
			}
		}
		return true;
	};
	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){
		cout<<ans[i];
	}

	// 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;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	149 ms	4612 KB	Output isn't correct
2	Incorrect	145 ms	4872 KB	Output isn't correct
3	Incorrect	148 ms	4984 KB	Output isn't correct
4	Incorrect	144 ms	4712 KB	Output isn't correct
5	Incorrect	143 ms	4672 KB	Output isn't correct
6	Incorrect	154 ms	4672 KB	Output isn't correct
7	Incorrect	143 ms	4684 KB	Output isn't correct
8	Incorrect	144 ms	4680 KB	Output isn't correct
9	Incorrect	153 ms	11736 KB	Output isn't correct
10	Incorrect	170 ms	11988 KB	Output isn't correct
11	Incorrect	51 ms	4176 KB	Output isn't correct
12	Incorrect	125 ms	7664 KB	Output isn't correct
13	Incorrect	196 ms	15180 KB	Output isn't correct
14	Incorrect	196 ms	16812 KB	Output isn't correct
15	Incorrect	362 ms	18468 KB	Output isn't correct
16	Incorrect	313 ms	27456 KB	Output isn't correct
17	Incorrect	384 ms	32284 KB	Output isn't correct
18	Incorrect	999 ms	24792 KB	Output isn't correct
19	Execution timed out	1036 ms	19024 KB	Time limit exceeded
20	Incorrect	376 ms	32644 KB	Output isn't correct