oj.uz

Submission #689462

# Submission time Handle Problem Language Result Execution time Memory
689462 2023-01-28T14:11:00 Z Rafiv Job Scheduling (CEOI12_jobs) C++14
100 / 100
 496 ms 26432 KB 
#include <bits/stdc++.h>
#define ll 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);
}

vector<pii> arr;
int k , d, n;

pair<bool, vector<vector<int>>> good(int x){
   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(){
   cin >> k >> d >> n;
   
   arr.resize(n);

   for(int i=0; i < n; i++){
      int ipt; cin >> ipt;

      arr[i] = {ipt, i+1};
   }

   // 
   

   sort(arr.begin(), arr.end());

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

   
   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(mid);
      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();
}

Compilation message

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2976 KB Output is correct
2 Correct 40 ms 3084 KB Output is correct
3 Correct 40 ms 2968 KB Output is correct
4 Correct 42 ms 3084 KB Output is correct
5 Correct 41 ms 2968 KB Output is correct
6 Correct 42 ms 2976 KB Output is correct
7 Correct 40 ms 3048 KB Output is correct
8 Correct 40 ms 2980 KB Output is correct
9 Correct 185 ms 9692 KB Output is correct
10 Correct 190 ms 9740 KB Output is correct
11 Correct 39 ms 2748 KB Output is correct
12 Correct 73 ms 4956 KB Output is correct
13 Correct 126 ms 8564 KB Output is correct
14 Correct 186 ms 10816 KB Output is correct
15 Correct 191 ms 10928 KB Output is correct
16 Correct 269 ms 16132 KB Output is correct
17 Correct 331 ms 18724 KB Output is correct
18 Correct 333 ms 23288 KB Output is correct
19 Correct 496 ms 26432 KB Output is correct
20 Correct 312 ms 18816 KB Output is correct