답안 #847113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847113	2023-09-09T07:23:04 Z	airths	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1000 ms	26292 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);
		}
		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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	157 ms	4360 KB	Expected EOLN
2	Incorrect	158 ms	4484 KB	Expected EOLN
3	Incorrect	160 ms	4480 KB	Expected EOLN
4	Incorrect	157 ms	4420 KB	Expected EOLN
5	Incorrect	158 ms	4424 KB	Expected EOLN
6	Incorrect	158 ms	4356 KB	Expected EOLN
7	Incorrect	157 ms	4436 KB	Expected EOLN
8	Incorrect	161 ms	4356 KB	Expected EOLN
9	Incorrect	145 ms	11184 KB	Expected EOLN
10	Incorrect	147 ms	11440 KB	Expected EOLN
11	Incorrect	65 ms	3064 KB	Expected EOLN
12	Incorrect	219 ms	5496 KB	Expected EOLN
13	Incorrect	271 ms	9660 KB	Expected EOLN
14	Incorrect	338 ms	12788 KB	Expected EOLN
15	Incorrect	397 ms	13404 KB	Expected EOLN
16	Incorrect	335 ms	16976 KB	Expected EOLN
17	Incorrect	522 ms	22740 KB	Expected EOLN
18	Execution timed out	1025 ms	22236 KB	Time limit exceeded
19	Execution timed out	1060 ms	26292 KB	Time limit exceeded
20	Incorrect	526 ms	22868 KB	Expected EOLN