제출 #689427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689427		Rafiv	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	571 ms	45380 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);
}

pair<bool, vector<vector<int>>> good(pii *arr, 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;
   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 = 1;
   int r = n;

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

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

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

  cout << l <<endl;

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





}




signed main(){
   BOOST
   solve();
}

   
 
  

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'void solve()':
jobs.cpp:72:8: warning: variable 'per' set but not used [-Wunused-but-set-variable]
   72 |    int per = 0;
      |        ^~~
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