Submission #689438

#	Time	Username	Problem	Language	Result	Execution time	Memory
689438		Rafiv	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	756 ms	45348 KiB

jobs

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pii pair<long long,long long>
#define pb push_back
#define fi first
#define se second
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;
//int range 1e9
//ll range 1e18
//double > float
// 1sec -> 1e8
const int MOD = 1e9 + 7;

void Usaco(string s) { 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}

pii arr[1000000];

pair<bool, vector<vector<int>>> good(int x, int k , int d, int n){
   vector<vector<int>> pros(k);
   int idx = 0;

   for(int days = 1; days <= k; days++){

      for(int j = 1; j<= x; j++){
         if(arr[idx].fi > days) break;

         if(arr[idx].fi + d >= days){
            pros[days-1].pb( arr[idx].se);
            idx++;
         }
         else return {false, pros};

         if(idx == n) return {true, pros};
      }
   }
   return {false, pros};
}

void solve(){
   int k , d, n;
   cin >> k >> d >> n;
   

   for(int i=0; i < n; i++){
      cin >> arr[i].fi;

      arr[i].se = i + 1;
   }

   // 
   

   sort(arr, arr + n);

   // for(int i=0; i < n; i++){
   //    cout << i << " " << arr[i].fi << endl;
   //    //arr[i].se = i + 1;
   // }
   //cout  << good(arr, 2 , k , d,n);

   // for(int i = 0;  i<= 50; i++){
   //    cout << i << " " << good(arr, i , k , d,n) << endl;
   // }

   int l = 1;
   int r = 1e12;

   int per = 0;
   vector<vector<int>> ked;

   while(l+1 < r){
      int mid = (l + r) / 2;

      pair<bool, vector<vector<int>>> res = good(mid, k , d , n);
      if(res.fi == true){
         per = mid;
         ked = res.se;
         r = mid;
      }
      else l = mid;
   }

  cout << per <<endl;

  for(int i = 0; i < k; i++){
   for(auto v  : ked[i]){
      cout << v << " ";
   }
   cout << 0 << endl;
  }





}




signed main(){
   BOOST
   solve();
}

   
 
  

Compilation message (stderr)

jobs.cpp: In function 'void Usaco(std::string)':
jobs.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100