oj.uz

Submission #1084527

# Submission time Handle Problem Language Result Execution time Memory
1084527 2024-09-06T11:09:20 Z rayan_bd Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 31136 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;++j){
			ans2[day].pb(ar[curr].second+1);
			--curr;
		}
	}
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4052 KB Output isn't correct
2 Incorrect 19 ms 4192 KB Output isn't correct
3 Incorrect 18 ms 4052 KB Output isn't correct
4 Incorrect 19 ms 4040 KB Output isn't correct
5 Incorrect 20 ms 4048 KB Output isn't correct
6 Incorrect 19 ms 4048 KB Output isn't correct
7 Incorrect 19 ms 4040 KB Output isn't correct
8 Incorrect 22 ms 4048 KB Output isn't correct
9 Incorrect 37 ms 6000 KB Output isn't correct
10 Incorrect 35 ms 5996 KB Output isn't correct
11 Incorrect 352 ms 3424 KB Output isn't correct
12 Incorrect 344 ms 6796 KB Expected EOLN
13 Incorrect 402 ms 10932 KB Output isn't correct
14 Execution timed out 1070 ms 8656 KB Time limit exceeded
15 Incorrect 438 ms 15536 KB Output isn't correct
16 Execution timed out 1025 ms 16832 KB Time limit exceeded
17 Execution timed out 1064 ms 16832 KB Time limit exceeded
18 Incorrect 535 ms 26780 KB Output isn't correct
19 Incorrect 544 ms 31136 KB Output isn't correct
20 Execution timed out 1080 ms 16828 KB Time limit exceeded