oj.uz

Submission #375268

# Submission time Handle Problem Language Result Execution time Memory
375268 2021-03-09T05:45:12 Z YJU Job Scheduling (CEOI12_jobs) C++14
0 / 100
 310 ms 65536 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e6+5;
const ll MOD=1e9+7;
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,st[N],d,m;
vector<ll> done[N],upd[N];
queue<ll> que;

bool ck(ll k){
	while(SZ(que))que.pop();
	REP1(i,n){
		done[i].clear();
		for(ll j:upd[i])que.push(j);
		REP(j,k){
			if(!SZ(que))break;
			done[i].pb(que.front());
			que.pop();
		}
		if(SZ(que)&&st[que.front()]+d<=i)return 0;
	}
	return 1;
}

void out(ll id){
	for(auto i:done[id])cout<<i<<" ";
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d>>m;
	REP1(i,m){
        cin>>st[i];
        upd[st[i]].pb(i);
	}
	ll r=m,l=-1;
	while(l<r-1){
		ll mid=(l+r)>>1;
		if(ck(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r<<"\n";
	REP1(i,n){
		for(auto j:done[i])cout<<j<<" ";
		cout<<"0\n";
	}
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4


*/

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 50284 KB Memory limit exceeded
2 Runtime error 60 ms 50156 KB Memory limit exceeded
3 Runtime error 64 ms 50156 KB Memory limit exceeded
4 Runtime error 63 ms 50156 KB Memory limit exceeded
5 Runtime error 61 ms 50156 KB Memory limit exceeded
6 Runtime error 63 ms 50156 KB Memory limit exceeded
7 Runtime error 60 ms 50156 KB Memory limit exceeded
8 Runtime error 60 ms 50156 KB Memory limit exceeded
9 Runtime error 69 ms 49600 KB Memory limit exceeded
10 Runtime error 67 ms 49644 KB Memory limit exceeded
11 Runtime error 65 ms 49388 KB Memory limit exceeded
12 Runtime error 91 ms 51456 KB Memory limit exceeded
13 Runtime error 121 ms 54764 KB Memory limit exceeded
14 Runtime error 180 ms 57068 KB Memory limit exceeded
15 Runtime error 173 ms 58420 KB Memory limit exceeded
16 Runtime error 238 ms 60908 KB Memory limit exceeded
17 Runtime error 292 ms 65536 KB Memory limit exceeded
18 Runtime error 278 ms 65536 KB Memory limit exceeded
19 Runtime error 310 ms 65536 KB Memory limit exceeded
20 Runtime error 307 ms 65536 KB Memory limit exceeded