Submission #1251855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251855		_rain_	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	203 ms	17560 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>(x))&(1))

template<class X , class Y>
	bool maximize(X &x , Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x, Y y){
		if (x>y) return x=y,true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end()) ; 
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	int Rand(int l,int r){
		return uniform_int_distribution<int>(l,r)(rng);
	}
	
const int N = (int) 1e6;
	int id[N+2] = {} , a[N+2] = {};
	int n , m , d;
	bool check(int length){
		int idx = 0;
		for(int i = 1; i <= n; ++i){
			
			for(int j = 1; j <= length; ++j){
				++idx;
				if (a[id[idx]]  > i){
					--idx;
					break;
				}
				if (idx == m) return true;
				if (i - a[id[idx]] > d) return false;
				
			}
		}
		return false;
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
	
		cin >> n >> d >> m;
		vector<int>nen;
		FOR(i,1,m) cin >> a[i] , id[i] = i , nen.push_back(a[i]);
		compress(nen);
		sort(id+1,id+m+1,[&](int i,int j){
			return a[i] < a[j];
		});

		int low = 1 , high = m , ans = -1;
		while (low<=high){
			int mid = (low+high) / 2;
			if (check(mid)){
				ans = mid , high = mid-1;
			}
			else low = mid + 1;
		}
		cout << ans << '\n';
		int idx = 0;
		for(int i = 1; i <= n; ++i){
			
			for(int j = 1; j <= ans; ++j){
				++idx;
				if (idx > m) break;
				if (a[id[idx]]  > i){
					--idx;
					break;
				}
				
				cout<<id[idx]<<' ';
			}	
			cout<<0<<'\n';
		}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:54:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:55:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100