oj.uz

Submission #1084558

# Submission time Handle Problem Language Result Execution time Memory
1084558 2024-09-06T11:39:17 Z rayan_bd Job Scheduling (CEOI12_jobs) C++17
33 / 100
 1000 ms 32936 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
 
 
#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
 
const int mxN = 1e6 + 500;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
 
vector<pair<ll,ll>> ar;
ll n,m,d,x;
 
bool good(ll mid){
	ll curr=m-1;
	for(ll day=min(n,ar[curr].first+d);day>=1&&curr>0;--day){
		for(ll j=0;j<mid&&curr>0;++j){
			if(ar[curr].first>day) return 0;
			if(ar[curr].first<=day&&day<=ar[curr].first+d) --curr;
		}
	}
	return curr==0;
}
 
void solve(ll tc) {
    cin>>n>>d>>m;
    for(ll i=0;i<m;++i){
    	cin>>x;
    	ar.pb({x,i});
    }
    sort(all(ar));
    ll start=1,end=1e5+10,ans=INF;
    while(start<=end){
    	ll mid=start+(end-start)/2;
    	if(good(mid)){
    		ans=mid;
    		end=mid-1;
    	}else{
    		start=mid+1;
    	}
    }
    vector<vector<ll>> ans2(n+1);
    ll curr=m-1;
	for(ll day=n;day>=1&&curr>0;--day){
		for(ll j=0;j<ans&&curr>0&&ar[curr].first+d<=day;++j){
			ans2[day].pb(ar[curr].second+1);
			--curr;
		}
	}
	cout<<ans<<nl;
	for(ll i=1;i<=n;++i){
		for(auto itt:ans2[i]){
			cout<<itt<<" ";
		}
		cout<<0;
		br;
	}
} 
 
int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    	
    solve(69);
 
    return 0;
}

Subtask #1
33.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 19 ms 4048 KB Partially correct
2 Partially correct 20 ms 4052 KB Partially correct
3 Partially correct 18 ms 4052 KB Partially correct
4 Partially correct 18 ms 4560 KB Partially correct
5 Partially correct 25 ms 4040 KB Partially correct
6 Partially correct 19 ms 4052 KB Partially correct
7 Partially correct 19 ms 4052 KB Partially correct
8 Partially correct 22 ms 4048 KB Partially correct
9 Partially correct 35 ms 6100 KB Partially correct
10 Partially correct 34 ms 6084 KB Partially correct
11 Partially correct 346 ms 2520 KB Partially correct
12 Correct 336 ms 5440 KB Output is correct
13 Partially correct 385 ms 10188 KB Partially correct
14 Execution timed out 1067 ms 10188 KB Time limit exceeded
15 Partially correct 408 ms 10192 KB Partially correct
16 Execution timed out 1050 ms 18624 KB Time limit exceeded
17 Execution timed out 1048 ms 17604 KB Time limit exceeded
18 Partially correct 519 ms 28080 KB Partially correct
19 Runtime error 540 ms 32936 KB Memory limit exceeded
20 Execution timed out 1027 ms 18616 KB Time limit exceeded