Submission #689306

#	Time	Username	Problem	Language	Result	Execution time	Memory
689306		Rafiv	Job Scheduling (CEOI12_jobs)	C++14	45 / 100	387 ms	21028 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;

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

         if(cnt == x){
            //cout << days << " " << i << " " << tmp << endl;
            if(days > tmp + d) return false;
            days++;
            cnt = 0;
            tmp = 1e10;
         }
         
      }

      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;
   // }

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

   int l = 0;
   int r = 1e10;

   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;

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

      cnt++;

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

   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 '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: 45 / 100