Submission #567947

#	Time	Username	Problem	Language	Result	Execution time	Memory
567947		imObscure	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	307 ms	20812 KiB

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){
  		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 (stderr)

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

• Subtask 1: 55 / 100