oj.uz

Submission #375269

# Submission time Handle Problem Language Result Execution time Memory
375269 2021-03-09T05:46:49 Z YJU Job Scheduling (CEOI12_jobs) C++14
0 / 100
 252 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,ll ty){
	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;
			if(ty)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,0)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r<<"\n";
	ck(r,1);
	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 59 ms 51688 KB Memory limit exceeded
2 Runtime error 58 ms 51688 KB Memory limit exceeded
3 Runtime error 59 ms 51688 KB Memory limit exceeded
4 Runtime error 62 ms 51688 KB Memory limit exceeded
5 Runtime error 59 ms 51672 KB Memory limit exceeded
6 Runtime error 61 ms 51688 KB Memory limit exceeded
7 Runtime error 60 ms 51688 KB Memory limit exceeded
8 Runtime error 65 ms 51688 KB Memory limit exceeded
9 Runtime error 64 ms 51052 KB Memory limit exceeded
10 Runtime error 65 ms 51052 KB Memory limit exceeded
11 Runtime error 61 ms 50796 KB Memory limit exceeded
12 Runtime error 92 ms 54380 KB Memory limit exceeded
13 Runtime error 117 ms 60268 KB Memory limit exceeded
14 Runtime error 183 ms 63468 KB Memory limit exceeded
15 Runtime error 180 ms 64252 KB Memory limit exceeded
16 Runtime error 252 ms 65536 KB Memory limit exceeded
17 Runtime error 213 ms 65540 KB Execution killed with signal 9
18 Runtime error 195 ms 65540 KB Execution killed with signal 9
19 Runtime error 210 ms 65540 KB Execution killed with signal 9
20 Runtime error 207 ms 65540 KB Execution killed with signal 9