Submission #642566

#	Time	Username	Problem	Language	Result	Execution time	Memory
642566		ymm	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	235 ms	24976 KiB

jobs

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int M = 1000010;

vector<int> a[N];
int n, m, d;

bool bin(int x)
{
	queue<int> q;
	Loop (i,0,N) {
		Loop (_,0,a[i].size())
			q.push(i+d);
		if (q.size() && q.front() <= i)
			return 0;
		for (int _=0; _<x && q.size(); ++_)
			q.pop();
	}
	return 1;
}

vector<vector<int>> plan(int x)
{
	vector<vector<int>> ans;
	queue<int> q;
	Loop (i,0,N) {
		for (int j : a[i])
			q.push(j);
		ans.emplace_back();
		for (int _=0; _<x && q.size(); ++_) {
			ans.back().push_back(q.front());
			q.pop();
		}
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> d >> m; ++d;
	Loop (i,0,m) {
		int x;
		cin >> x;
		a[x-1].push_back(i+1);
	}
	int l = 1, r = m;
	while (l < r) {
		int mid = (l+r)/2;
		if (bin(mid))
			r = mid;
		else
			l = mid+1;
	}
	cout << l << '\n';
	auto ans = plan(l);
	Loop (i,0,n) {
		for (int j : ans[i])
			cout << j << ' ';
		cout << "0\n";
	}
}

Compilation message (stderr)

jobs.cpp: In function 'bool bin(int)':
jobs.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
jobs.cpp:19:3: note: in expansion of macro 'Loop'
   19 |   Loop (_,0,a[i].size())
      |   ^~~~

• Subtask 1: 100 / 100