Submission #1251768

#TimeUsernameProblemLanguageResultExecution timeMemory
1251768_rain_Job Scheduling (CEOI12_jobs)C++20
0 / 100
271 ms111360 KiB
#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;
const int MAXLOG = (int)18;	
	vector<int>days[N+2];
	int rmq[N+2][MAXLOG+2] = {} , LOG[N+2] = {} , id[N+2] = {} , a[N+2] = {};
	int n , m , d;
	
	int Get(int l,int r){
		int x = LOG[r-l+1];
		return min(rmq[l][x] , rmq[r-(1<<x)+1][x]);
	}
	
	bool check(int length){
		for(int i = 1 , cur = 1; i <= m; i += length , ++cur){
			int x = min(m , i + length - 1);
			
			if (Get(i,x) + d < cur) return false;
		}
		return true;
	}

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;
		FOR(i,1,m) cin >> a[i] , id[i] = i;
		sort(id+1,id+m+1,[&](int i,int j){
			return a[i] < a[j];
		});
		FOR(i,1,m) rmq[i][0] = a[id[i]];
		FOR(i,2,m) LOG[i] = LOG[i/2] + 1;
		FOR(j,1,MAXLOG){
			FOR(i,1,m-(1<<j)+1) rmq[i][j] = min(rmq[i][j-1] , rmq[i+(1<<(j-1))][j-1]);
		}
		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 = 1;
		for(int i = 1; i <= n; ++i){
			for(int j = idx; j <= min(m , idx + ans - 1);  ++j) cout << id[j] << ' '; cout << 0 << '\n';
			idx += ans;
		}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:53:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...