oj.uz

답안 #637818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637818 2022-09-03T11:10:19 Z beaconmc Job Scheduling (CEOI12_jobs) C++14
100 / 100
 405 ms 13848 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=(x); i<(y); i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll int

ll temp;
ll n,d,m;
ll lis[1000001];
vector<pair<ll,ll>> sus;

bool check(ll x){
	ll cur = 0;
	FOR(i,0,m){
		cur += lis[i];
		cur -= min(cur,x);
		if (cur > x*d){
			return false;
		}
	}
	return true;
}

void ans(ll x){
	vector<ll> realsus;
	queue<pair<ll,ll>> q;
	ll cur = 0;
	FOR(i,0,n){
		while (cur<m && sus[cur].first == i+1){
			q.push(sus[cur]);
			cur++;
		}

		ll sus = q.size();
		sus = min(sus,x);


		FOR(j,0,sus){
			cout << q.front().second << " ";
			q.pop();
		}
		cout << 0 << "\n";

	}
}

int main(){
	cin >> n >> d >> m;

	FOR(i,0,m){
		cin >> temp;
		lis[temp-1] += 1;

		sus.push_back(make_pair(temp,i+1));
	}
	sort(sus.begin(),sus.end());

	ll lo = 0;
	ll hi = 1000001;

	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}else{
			lo = mid+1;
		}
	}
	cout << lo << "\n";
	ans(lo);

	


	

}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 2576 KB Output is correct
2 Correct 31 ms 2524 KB Output is correct
3 Correct 31 ms 2496 KB Output is correct
4 Correct 31 ms 2504 KB Output is correct
5 Correct 30 ms 2516 KB Output is correct
6 Correct 31 ms 2480 KB Output is correct
7 Correct 30 ms 2492 KB Output is correct
8 Correct 30 ms 2444 KB Output is correct
9 Correct 43 ms 2108 KB Output is correct
10 Correct 43 ms 1908 KB Output is correct
11 Correct 40 ms 1712 KB Output is correct
12 Correct 81 ms 3336 KB Output is correct
13 Correct 121 ms 4696 KB Output is correct
14 Correct 177 ms 6536 KB Output is correct
15 Correct 200 ms 7724 KB Output is correct
16 Correct 287 ms 9300 KB Output is correct
17 Correct 308 ms 10736 KB Output is correct
18 Correct 331 ms 12324 KB Output is correct
19 Correct 405 ms 13848 KB Output is correct
20 Correct 307 ms 10844 KB Output is correct