oj.uz

Submission #932933

# Submission time Handle Problem Language Result Execution time Memory
932933 2024-02-24T14:56:35 Z serifefedartar Job Scheduling (CEOI12_jobs) C++17
30 / 100
 233 ms 18456 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 998244353;
const ll MAXN = 1e5 + 100;

int N, D;
vector<vector<int>> ans;
vector<int> days[MAXN];
deque<pair<int,int>> dq;

bool check(int mid) {
	dq = deque<pair<int,int>>();
	ans.clear();
	for (int i = 1; i <= N; i++) {
		ans.emplace_back(vector<int>());
		for (auto u : days[i]) {
			dq.push_back({i + D, u});
		}

		int Q = mid;
		while (Q && dq.size()) {
			pair<int,int> P = dq.front();
			if (P.f < i)
				return false;
			ans.back().push_back(P.s);
			dq.pop_front();
			Q--;
		}
	}

	return dq.empty();
}

int main() {
	fast
	int M, Q;
	cin >> N >> D >> M;

	for (int i = 0; i < M; i++) {
		cin >> Q;
		days[Q].push_back(i+1);
	}

	int L = 1;
	int R = M;
	int res = -1;
	while (R >= L) {
		int mid = L + (R - L) / 2;
		if (check(mid)) {
			res = mid;
			R = mid - 1;
		} else
			L = mid + 1;
	}
	
	cout << res << endl;
	for (auto u : ans) {
		for (auto v : u)
			cout << v << " ";
		cout << "0" << endl;
	}
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 5148 KB Unexpected end of file - int32 expected
2 Incorrect 22 ms 5136 KB Unexpected end of file - int32 expected
3 Incorrect 23 ms 5136 KB Unexpected end of file - int32 expected
4 Incorrect 23 ms 5176 KB Unexpected end of file - int32 expected
5 Incorrect 23 ms 5192 KB Unexpected end of file - int32 expected
6 Incorrect 23 ms 5144 KB Unexpected end of file - int32 expected
7 Incorrect 23 ms 5108 KB Unexpected end of file - int32 expected
8 Incorrect 23 ms 5244 KB Unexpected end of file - int32 expected
9 Incorrect 27 ms 7676 KB Unexpected end of file - int32 expected
10 Incorrect 26 ms 7144 KB Unexpected end of file - int32 expected
11 Correct 31 ms 4436 KB Output is correct
12 Correct 57 ms 6232 KB Output is correct
13 Incorrect 71 ms 9032 KB Unexpected end of file - int32 expected
14 Correct 135 ms 11068 KB Output is correct
15 Correct 112 ms 10976 KB Output is correct
16 Correct 174 ms 14136 KB Output is correct
17 Incorrect 221 ms 18020 KB Unexpected end of file - int32 expected
18 Correct 228 ms 17060 KB Output is correct
19 Incorrect 233 ms 18456 KB Unexpected end of file - int32 expected
20 Incorrect 209 ms 18024 KB Unexpected end of file - int32 expected