oj.uz

Submission #932917

# Submission time Handle Problem Language Result Execution time Memory
932917 2024-02-24T14:01:36 Z serifefedartar Job Scheduling (CEOI12_jobs) C++17
30 / 100
 239 ms 21624 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.push_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 5472 KB Unexpected end of file - int32 expected
2 Incorrect 23 ms 5500 KB Unexpected end of file - int32 expected
3 Incorrect 23 ms 5404 KB Unexpected end of file - int32 expected
4 Incorrect 23 ms 5448 KB Unexpected end of file - int32 expected
5 Incorrect 23 ms 5440 KB Unexpected end of file - int32 expected
6 Incorrect 23 ms 5448 KB Unexpected end of file - int32 expected
7 Incorrect 23 ms 5624 KB Unexpected end of file - int32 expected
8 Incorrect 23 ms 5624 KB Unexpected end of file - int32 expected
9 Incorrect 28 ms 8368 KB Unexpected end of file - int32 expected
10 Incorrect 27 ms 8680 KB Unexpected end of file - int32 expected
11 Correct 24 ms 4700 KB Output is correct
12 Correct 49 ms 7004 KB Output is correct
13 Incorrect 72 ms 10084 KB Unexpected end of file - int32 expected
14 Correct 124 ms 13096 KB Output is correct
15 Correct 123 ms 12808 KB Output is correct
16 Correct 163 ms 17036 KB Output is correct
17 Incorrect 195 ms 21456 KB Unexpected end of file - int32 expected
18 Correct 210 ms 20116 KB Output is correct
19 Incorrect 239 ms 21624 KB Unexpected end of file - int32 expected
20 Incorrect 196 ms 21352 KB Unexpected end of file - int32 expected