oj.uz

Submission #1084567

# Submission time Handle Problem Language Result Execution time Memory
1084567 2024-09-06T11:46:36 Z rayan_bd Job Scheduling (CEOI12_jobs) C++17
60 / 100
 189 ms 31148 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&&ar[curr].first<=day&&day<=ar[curr].first+d;++j){
			--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 9 ms 2516 KB Output isn't correct
2 Incorrect 10 ms 2520 KB Output isn't correct
3 Incorrect 9 ms 2516 KB Output isn't correct
4 Incorrect 9 ms 2520 KB Output isn't correct
5 Incorrect 10 ms 2540 KB Output isn't correct
6 Incorrect 10 ms 2520 KB Output isn't correct
7 Incorrect 9 ms 2520 KB Output isn't correct
8 Incorrect 9 ms 2520 KB Output isn't correct
9 Correct 25 ms 6016 KB Output is correct
10 Correct 25 ms 6104 KB Output is correct
11 Correct 20 ms 3536 KB Output is correct
12 Correct 39 ms 7568 KB Output is correct
13 Correct 63 ms 12976 KB Output is correct
14 Correct 84 ms 14772 KB Output is correct
15 Correct 95 ms 15544 KB Output is correct
16 Correct 128 ms 19368 KB Output is correct
17 Correct 150 ms 27568 KB Output is correct
18 Correct 160 ms 26792 KB Output is correct
19 Correct 189 ms 31148 KB Output is correct
20 Correct 147 ms 27236 KB Output is correct