oj.uz

답안 #1084306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084306 2024-09-05T20:01:28 Z 4QT0R Job Scheduling (CEOI12_jobs) C++17
90 / 100
 105 ms 20560 KB 
#include <bits/stdc++.h>
using namespace std;

int zle[100003];
int wej[1000003];
vector<int> ans[100003];

deque<pair<int,int>> dq;
queue<int> q;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,d,m;
	cin >> n >> d >> m;
	for (int i = 1; i<=m; i++){
		cin >> wej[i];
		zle[wej[i]]++;
		ans[wej[i]].push_back(i);
	}
	int l=1,p=m,md;
	while(l<p){
		md=(l+p)/2;
		bool ok=true;
		for (int i = 1; i<=n; i++){
			dq.push_back({zle[i],i});
			int lft=md;
			while(dq.size() && lft){
				auto [z,ind] = dq.front();
				dq.pop_front();
				if (lft>=z){
					lft-=z;
					z=0;
				}
				else{
					z-=lft;
					lft=0;
					dq.push_front({z,ind});
				}
			}
			if (dq.size() && dq.front().second+d<=i){
				ok=false;
				dq.clear();
				break;
			}
		}
		if (dq.size())ok=false;
		dq.clear();
		if (ok)p=md;
		else l=md+1;
	}
	cout << l << '\n';
	for (int i = 1; i<=n; i++){
		for (auto u : ans[i])q.push(u);
		for (int j = 1; j<=l; j++){
			if (q.empty())break;
			cout << q.front() << ' ';
			q.pop();
		}
		cout << "0\n";
	}
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4828 KB Output is correct
2 Correct 11 ms 4828 KB Output is correct
3 Correct 11 ms 4828 KB Output is correct
4 Correct 12 ms 4828 KB Output is correct
5 Correct 13 ms 4824 KB Output is correct
6 Correct 11 ms 4828 KB Output is correct
7 Correct 11 ms 4828 KB Output is correct
8 Correct 13 ms 4752 KB Output is correct
9 Correct 17 ms 4700 KB Output is correct
10 Correct 18 ms 4700 KB Output is correct
11 Correct 13 ms 4696 KB Output is correct
12 Incorrect 27 ms 6480 KB Output isn't correct
13 Correct 33 ms 9300 KB Output is correct
14 Incorrect 56 ms 11600 KB Output isn't correct
15 Correct 71 ms 12880 KB Output is correct
16 Correct 84 ms 16036 KB Output is correct
17 Correct 89 ms 18772 KB Output is correct
18 Correct 91 ms 18772 KB Output is correct
19 Correct 105 ms 20560 KB Output is correct
20 Correct 91 ms 18824 KB Output is correct