Submission #1140933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140933		settop	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	195 ms	20148 KiB

jobs

#include<bits/stdc++.h>
 
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
const int MAXN=1e5+10;
const ll inf=0X3f3f3f3f3f3f3f3f;
const int infi=0X3f3f3f3f;
const ll MOD=998244353;
 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll,ll> trio;

int n,d,m,ans;
vector<pii> v;
vector<int> aux[MAXN];

bool test(int x){
	queue<int> fila;
	int l=0,r=1,q=1;
	while(r<=n){
		while(l<m && v[l].F<=r){
			fila.push(v[l].F);
			l++;
		}
		while(!fila.empty() && q<=x){
			auto u=fila.front();
			if(r-u>d)
				return false;
			fila.pop();
			q++;
		}
		r++;
		q=1;
	}
	if(!fila.empty())
		return false;
	return true;
}

void f(int x){
	queue<pii> fila;
	int l=0,r=1,q=1;
	while(r<=n){
		while(l<m && v[l].F<=r){
			fila.push({v[l].F,v[l].S});
			l++;
		}
		while(!fila.empty() && q<=x){
			auto u=fila.front();
			fila.pop();
			aux[r].pb(u.S);
			q++;
		}
		r++;
		q=1;
	}
	fall(i,1,n){
		for(auto u:aux[i])cout<<u<<" ";
		cout<<"0\n";
	}
}

int32_t main(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("angry.in","r",stdin);
	//freopen("angry.out","w",stdout);

	cin>>n>>d>>m;
	v.resize(m);
	fall(i,0,m-1){
		cin>>v[i].F;
		v[i].S=i+1;
	}
	sort(all(v));
	int ini=0,fim=m;
	while(ini<=fim){
		int mei=(ini+fim)/2;
		if(test(mei)){
			ans=mei;
			fim=mei-1;
		}
		else ini=mei+1;
	}
	cout<<ans<<"\n";
	f(ans);
}

• Subtask 1: 100 / 100