oj.uz

Submission #344458

# Submission time Handle Problem Language Result Execution time Memory
344458 2021-01-05T20:08:33 Z chienyu_xiong Job Scheduling (CEOI12_jobs) C++14
10 / 100
 275 ms 18056 KB 
#include <bits/stdc++.h>

#define F first
#define S second

#define pb push_back
#define mp make_pair

typedef long long int lli;

#define pll pair<lli, lli>
#define pil pair<int, lli>
#define pli pair<lli, int>
#define pii pair<int, int>

using namespace std;

void setIO(string str, bool dbg) {
	ios_base::sync_with_stdio(0);

	cin.tie(0);
	cout.tie(0);

	if (!dbg) {
		freopen((str + ".in").c_str(), "r", stdin);
		freopen((str + ".out").c_str(), "w", stdout);
	}
}

const int MAX = 1e6 + 5;
const int LEN = 2e3 + 5;
const lli MOD = 1e9 + 7;
const lli INF = 1e17;

int _ = 1; // test cases

int n, m, d;
int arr[MAX];
int ord[MAX];

bool slv(int num) {
	vector<int> cnt(num);

	int cur = 0;
	for (int i = 0; i < n; i++) {
		cnt[cur] = max(arr[ord[i]], cnt[cur] + 1);
		if (cnt[cur] - arr[ord[i]] > d)
			return false;
		cur = (cur + 1) % num;
	}
	return true;
}

bool cmp(int a, int b) {
	return arr[a] < arr[b];
}

void fnc() {
	cin >> n >> d >> m;

	for (int i = 0; i < m; i++)
		cin >> arr[i], ord[i] = i;
	
	sort(ord, ord + m, cmp);

	int lo = 1;
	int hi = m;
	while (lo < hi) {
		int mid = (lo + hi + 0) / 2; // round down

		bool can = slv(mid);
		if (can == 1) hi = mid;
		if (can == 0) lo = mid + 1;
	}

	cout << lo << "\n";

	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		cout << ord[i - 1] + 1 << " ";
		if (i == m || i % lo == 0)
			cout << "0\n", cnt++;
	}
	for (int i = cnt; i < n; i++)
		cout << "0\n";
}

int main() {
	setIO("", 1);

	while (_--) fnc();

	return 0;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string, bool)':
jobs.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   freopen((str + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   freopen((str + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2216 KB Output isn't correct
2 Incorrect 21 ms 2236 KB Output isn't correct
3 Incorrect 21 ms 2216 KB Output isn't correct
4 Incorrect 21 ms 2216 KB Output isn't correct
5 Incorrect 21 ms 2216 KB Output isn't correct
6 Incorrect 21 ms 2216 KB Output isn't correct
7 Incorrect 21 ms 2216 KB Output isn't correct
8 Incorrect 21 ms 2216 KB Output isn't correct
9 Correct 35 ms 2344 KB Output is correct
10 Correct 35 ms 2344 KB Output is correct
11 Incorrect 28 ms 2216 KB Output isn't correct
12 Incorrect 68 ms 4196 KB Output isn't correct
13 Incorrect 89 ms 6304 KB Output isn't correct
14 Incorrect 130 ms 8668 KB Output isn't correct
15 Incorrect 143 ms 10136 KB Output isn't correct
16 Incorrect 193 ms 12760 KB Output isn't correct
17 Incorrect 227 ms 14924 KB Output isn't correct
18 Incorrect 237 ms 16076 KB Output isn't correct
19 Incorrect 275 ms 18056 KB Output isn't correct
20 Incorrect 228 ms 14736 KB Output isn't correct