oj.uz

Submission #1084526

# Submission time Handle Problem Language Result Execution time Memory
1084526 2024-09-06T11:08:03 Z rayan_bd Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 17080 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=n;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 Execution timed out 1042 ms 2516 KB Time limit exceeded
2 Execution timed out 1083 ms 2520 KB Time limit exceeded
3 Execution timed out 1045 ms 2520 KB Time limit exceeded
4 Execution timed out 1076 ms 2520 KB Time limit exceeded
5 Execution timed out 1035 ms 2772 KB Time limit exceeded
6 Execution timed out 1052 ms 2520 KB Time limit exceeded
7 Execution timed out 1063 ms 2520 KB Time limit exceeded
8 Execution timed out 1035 ms 2516 KB Time limit exceeded
9 Execution timed out 1010 ms 2516 KB Time limit exceeded
10 Execution timed out 1004 ms 2516 KB Time limit exceeded
11 Incorrect 398 ms 3424 KB Output isn't correct
12 Incorrect 392 ms 6836 KB Expected EOLN
13 Incorrect 446 ms 10928 KB Output isn't correct
14 Execution timed out 1066 ms 8656 KB Time limit exceeded
15 Incorrect 500 ms 15532 KB Output isn't correct
16 Execution timed out 1045 ms 16840 KB Time limit exceeded
17 Execution timed out 1069 ms 16844 KB Time limit exceeded
18 Execution timed out 1033 ms 17080 KB Time limit exceeded
19 Execution timed out 1063 ms 16832 KB Time limit exceeded
20 Execution timed out 1043 ms 16832 KB Time limit exceeded