oj.uz

Submission #932932

# Submission time Handle Problem Language Result Execution time Memory
932932 2024-02-24T14:51:46 Z serifefedartar Job Scheduling (CEOI12_jobs) C++17
30 / 100
 256 ms 20660 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 << "\n";
	for (auto u : ans) {
		for (auto v : u)
			cout << v << " ";
		cout << "0\n";
	}
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 5396 KB Unexpected end of file - int32 expected
2 Incorrect 28 ms 5520 KB Unexpected end of file - int32 expected
3 Incorrect 23 ms 5660 KB Unexpected end of file - int32 expected
4 Incorrect 23 ms 5448 KB Unexpected end of file - int32 expected
5 Incorrect 23 ms 5444 KB Unexpected end of file - int32 expected
6 Incorrect 29 ms 5612 KB Unexpected end of file - int32 expected
7 Incorrect 23 ms 5620 KB Unexpected end of file - int32 expected
8 Incorrect 23 ms 5624 KB Unexpected end of file - int32 expected
9 Incorrect 30 ms 7168 KB Unexpected end of file - int32 expected
10 Incorrect 26 ms 7912 KB Unexpected end of file - int32 expected
11 Correct 30 ms 4664 KB Output is correct
12 Correct 50 ms 6624 KB Output is correct
13 Incorrect 72 ms 9808 KB Unexpected end of file - int32 expected
14 Correct 132 ms 12424 KB Output is correct
15 Correct 112 ms 12236 KB Output is correct
16 Correct 159 ms 16068 KB Output is correct
17 Incorrect 210 ms 20068 KB Unexpected end of file - int32 expected
18 Correct 207 ms 18692 KB Output is correct
19 Incorrect 256 ms 20660 KB Unexpected end of file - int32 expected
20 Incorrect 196 ms 20104 KB Unexpected end of file - int32 expected