Submission #567949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
567949	2022-05-24T11:45:47 Z	imObscure	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	241 ms	20772 KB

jobs

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define indexed_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long ll;
using namespace std;

int xor1(int n){ if (n % 4 == 0) return n; if (n % 4 == 1) return 1; if (n % 4 == 2) return n + 1; return 0;}
template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
ll mod=1e9 + 7;
#define test ll t;cin>>t;while(t--)
#define mp make_pair
#define all(a) a.begin(),a.end()
#define pb push_back
#define re(i,n) for(ll i=0;i<n;i++)
#define reb(i,n) for(ll i=n-1;i>=0;i--)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef map<ll,int> ml;
typedef map<char,ll> mc;
typedef map<string,ll> ms;
typedef vector<pair<ll,ll>> vpl;
#define fi first
#define se second

using namespace std::chrono;



int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n,d,m; cin>>n>>d>>m;
  vpl v(m);
  re(i,m){
  	cin>>v[i].fi;
  	
  	v[i].se=i+1;
  }
  
  sort(all(v));
  
  auto chk=[&](ll x){
  	ll day=1,cnt=0;
  	re(i,m){
  		
  		while(day<=n && v[i].fi>day){day++; cnt=0;}
  		
  		if(day>n)return 0;
        if(cnt==x){
        	cnt=0;
        	day++;
        }
        if(day>n)return 0;
  		cnt++;
  		if((v[i].fi+d)<(day)){
  			return 0;
  		} 
  	}
  	return 1;
  };
  
  // for(auto x:v)cout<<x.fi<<" ";
  // cout<<'\n';
  
  ll lo=1,hi=m,ans=0;
  
  while(lo<hi){
  	ll mid=(lo+hi)/2;
  	//cout<<mid<<'\n';
  	if(chk(mid)){
  		ans=mid;
  		hi=mid;
  	}
  	else lo=mid+1;
  }
  
  cout<<lo<<'\n';
  int it=0;
  re(i,n){
  	int cnt=0;
  	while(it<m){
  		cnt++;
  		cout<<v[it].se<<" ";
  		it++;
  		if(cnt==lo)break;
  	}
  	cout<<"0\n";
  	
  }

 	return 0;
 }

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:76:16: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   76 |   ll lo=1,hi=m,ans=0;
      |                ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	2516 KB	Output is correct
2	Correct	19 ms	2472 KB	Output is correct
3	Correct	18 ms	2416 KB	Output is correct
4	Correct	17 ms	2408 KB	Output is correct
5	Correct	17 ms	2512 KB	Output is correct
6	Correct	16 ms	2516 KB	Output is correct
7	Correct	19 ms	2408 KB	Output is correct
8	Correct	18 ms	2416 KB	Output is correct
9	Correct	34 ms	2764 KB	Output is correct
10	Correct	25 ms	2660 KB	Output is correct
11	Correct	24 ms	2444 KB	Output is correct
12	Correct	51 ms	4740 KB	Output is correct
13	Correct	89 ms	6928 KB	Output is correct
14	Correct	105 ms	9292 KB	Output is correct
15	Correct	130 ms	11540 KB	Output is correct
16	Correct	166 ms	13800 KB	Output is correct
17	Correct	180 ms	16020 KB	Output is correct
18	Correct	209 ms	18352 KB	Output is correct
19	Correct	241 ms	20772 KB	Output is correct
20	Correct	186 ms	16156 KB	Output is correct