Submission #689326

#	Time	Username	Problem	Language	Result	Execution time	Memory
689326		Rafiv	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	553 ms	29756 KiB

jobs

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pii pair<int,int>
#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);
}

bool good(pii *arr, int x, int k , int d, int n){
      if(x == 0) return false;

      int tmp = 1e10;
      int cnt = 0;
      int days = 1;

      vector<int>res;

      for(int i=0; i < n; i++){
         tmp = max(tmp, arr[i].fi);
         res.pb(arr[i].fi);
         cnt++;

         if(res.size() == x){
            for(auto it : res){
               //cout << it << " ";
               if(days > it + d){
                  return false;
               }
            }
            //cout << endl;
            res.clear();
            days++;
            cnt = 0;
            //cout << days << " " << i << " " << tmp << endl;
            //if(days > tmp + d) return false;
         }
         
      }

      if(!res.empty()){
         for(auto it : res){
            if(days > it + d) return false;
         }
         
      }

      return true;
}

void solve(){
   int k , d, n;
   cin >> k >> d >> n;
   pii arr[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 = 0;
   int r = 1e12;

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

      if(good(arr, mid, k , d , n)) r = mid;
      else l = mid;
   }

   cout << r << endl;

   int cnt = 0;
   int times = 0;

   for(int i = 0; i < n; i++){
      cout << arr[i].se << " ";

      cnt++;

      if(cnt == r){
         cout << 0 << endl;
         cnt = 0;
         times++;
      }

      if(times > k) break;
   }

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





}




signed main(){
   BOOST
   solve();
}

   
 
  

Compilation message (stderr)

jobs.cpp: In function 'bool good(std::pair<long long int, long long int>*, long long int, long long int, long long int, long long int)':
jobs.cpp:36:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   36 |          if(res.size() == x){
      |             ~~~~~~~~~~~^~~~
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: 55 / 100