Submission #91390

#	Time	Username	Problem	Language	Result	Execution time	Memory
91390		Nordway	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	172 ms	33792 KiB

jobs

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

typedef unsigned long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const ll INF = 1e18;
const ll inf = 1e9;
const int mod = 998244353;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int N = 1e5+5;
const int M = 1e6+1;

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

bool check(int k){
	int cnt=a[1].x,cur=0;
	for(int i=1;i<=m;i++){
		if(a[i].x>cnt)cnt=a[i].x,cur=0;
		cur++;
		if(cur>k)cnt++,cur=1;
		if(a[i].x+d<=cnt)return 0;
	}
	if(cnt>n)return 0;
	else return 1;
}

void solve(int k){
	int cnt=a[1].x,cur=0;
	for(int i=1;i<=m;i++){
		if(a[i].x>cnt)cnt=a[i].x,cur=0;
		cur++;
		if(cur>k)cnt++,cur=1;
		g[cnt].pb(a[i].y);
	}
}

int main(){
	boost;
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x;
		a[i].y=i;
	}
	sort(a+1,a+m+1);
	int l=1,r=m,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
	solve(ans);
	for(int i=1;i<=n;i++){
		for(int j=0;j<sz(g[i]);j++){
			cout<<g[i][j]<<" ";
		}
		cout<<"0"<<endl;
	}
}

• Subtask 1: 5 / 100