oj.uz

Submission #1084566

# Submission time Handle Problem Language Result Execution time Memory
1084566 2024-09-06T11:45:22 Z rayan_bd Job Scheduling (CEOI12_jobs) C++17
60 / 100
 539 ms 31132 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=n+1,ans=n+1;
    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&&ar[curr].first<=day;++j){
			ans2[day].pb(ar[curr--].second+1);
		}
	}
	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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2516 KB Output isn't correct
2 Incorrect 9 ms 2684 KB Output isn't correct
3 Incorrect 9 ms 2520 KB Output isn't correct
4 Incorrect 10 ms 2588 KB Output isn't correct
5 Incorrect 9 ms 2516 KB Output isn't correct
6 Incorrect 10 ms 2520 KB Output isn't correct
7 Incorrect 10 ms 2520 KB Output isn't correct
8 Incorrect 9 ms 2520 KB Output isn't correct
9 Correct 34 ms 6096 KB Output is correct
10 Correct 34 ms 6108 KB Output is correct
11 Correct 23 ms 3540 KB Output is correct
12 Correct 44 ms 6848 KB Output is correct
13 Correct 67 ms 11180 KB Output is correct
14 Correct 392 ms 14776 KB Output is correct
15 Correct 114 ms 15544 KB Output is correct
16 Correct 462 ms 19196 KB Output is correct
17 Correct 493 ms 26384 KB Output is correct
18 Correct 213 ms 26780 KB Output is correct
19 Correct 539 ms 31132 KB Output is correct
20 Correct 491 ms 26268 KB Output is correct