Submission #635271

#	Time	Username	Problem	Language	Result	Execution time	Memory
635271		Anthony_Liu	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	371 ms	7372 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pb push_back
#define pi pair <int,int>
#define vi vector <int>
#define size(x) (int)(x).size()
#define all(x) x.begin(), x.end()
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (size(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int N, D, M;
vector <pi> v;

bool check(int m)
{
	priority_queue <int> waiting;
	for (int i=0; i<M; ++i)
	{
		/*/
		if (m == 1)
		{
			if (!waiting.empty()) cout<<waiting.top()<<'\n';
			else cout<<"empty"<<'\n';
			cout<<"size: "<<size(waiting)<<'\n';
		}
		/*/
		int cur = 1;
		while (!waiting.empty()) {
			if (cur >= m) break;
			waiting.pop();
			++cur;
		}
		if (! waiting.empty() && -waiting.top()+D <= v[i].f) 
			return false;
			
		while (v[i+1].f == v[i].f) {
			++i;
			waiting.push(-v[i].f);
		}
	}
	return (size(waiting) <= m);
}
int main()
{
	setIO();
	cin>>N>>D>>M;
	v.resize(M);
	for (int i=0; i<M; i++) {
		cin>>v[i].f;
		v[i].s = i;
	}
	sort (all(v));
	//for (auto k:v) cout<<k.f<<" "; cout<<'\n';
	
	int l = 1, r = M, m, ans;
	while (l <= r)
	{
		m = l+(r-l)/2;
		//cout<<m<<'\n';
		if (check(m)) {
			ans = m;
			r = m-1;
		}
		else l = m+1;
	}
	cout<<ans<<"\n";
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message (stderr)

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:74:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |  cout<<ans<<"\n";
      |             ^~~~

• Subtask 1: 0 / 100