Submission #344459

#	Time	Username	Problem	Language	Result	Execution time	Memory
344459		chienyu_xiong	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	368 ms	14728 KiB

jobs

#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 < m; 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 (stderr)

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: 100 / 100