oj.uz

Submission #375267

# Submission time Handle Problem Language Result Execution time Memory
375267 2021-03-09T05:44:35 Z YJU Job Scheduling (CEOI12_jobs) C++14
0 / 100
 215 ms 65540 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long 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 64 ms 52388 KB Memory limit exceeded
2 Runtime error 62 ms 52328 KB Memory limit exceeded
3 Runtime error 62 ms 52328 KB Memory limit exceeded
4 Runtime error 63 ms 52328 KB Memory limit exceeded
5 Runtime error 62 ms 52328 KB Memory limit exceeded
6 Runtime error 62 ms 52328 KB Memory limit exceeded
7 Runtime error 61 ms 52456 KB Memory limit exceeded
8 Runtime error 74 ms 52328 KB Memory limit exceeded
9 Runtime error 75 ms 51052 KB Memory limit exceeded
10 Runtime error 69 ms 51052 KB Memory limit exceeded
11 Runtime error 65 ms 50796 KB Memory limit exceeded
12 Runtime error 93 ms 54380 KB Memory limit exceeded
13 Runtime error 133 ms 60268 KB Memory limit exceeded
14 Runtime error 215 ms 64596 KB Memory limit exceeded
15 Runtime error 185 ms 65536 KB Memory limit exceeded
16 Runtime error 192 ms 65540 KB Execution killed with signal 9
17 Runtime error 141 ms 65540 KB Execution killed with signal 9
18 Runtime error 122 ms 65540 KB Execution killed with signal 9
19 Runtime error 125 ms 65540 KB Execution killed with signal 9
20 Runtime error 140 ms 65540 KB Execution killed with signal 9