Submission #699629

#	Time	Username	Problem	Language	Result	Execution time	Memory
699629		edev1	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	475 ms	20280 KiB

jobs

#include <bits/stdc++.h> 
#include <set> 
#include <map> 
#include <unordered_map> 
#include <vector> 
#include <utility> //pair
#include <string>
#define F first 
#define S second 
#define PB push_back 
#define MP make_pair 
typedef long long ll; 
using namespace std;

int n, d, m;

vector<pair<int,int>> vp;
vector<vector<int>> for_ans (100001);

void make_ans(int ans){
    int placed = 0;
    int i = 0;
    int day = 1;
    while(i < m){
        if(day >= vp[i].first && day <= vp[i].first + d){
            placed++;
            for_ans[day].push_back(++vp[i].second);
            if(placed == ans){
                if(i != m-1)
                    day++;
                placed = 0;
            }
        }else{
            day = vp[i].first;
            continue;
        }
        i++;
    }

    int j;
    for(int i = 1; i<=n; i++){
        j = 0;
        while(j < for_ans[i].size()){
            cout << for_ans[i][j] << " ";
            j++;
        }
        cout << 0 << endl;
    }
}

bool check(int x){
    int placed = 0;
    int i = 0;
    int day = 1;
    while(i < m){
        if(day >= vp[i].first && day <= vp[i].first + d){
            placed++;
            if(placed == x){
                if(i != m-1)
                    day++;
                placed = 0;
            }
        }else{
            if(day > vp[i].first + d){
                return false;
            }
            day = vp[i].first;
            continue;
        }
        i++;

    }

    if(day <= n){
        return true;
    }
    return false;
}

int main() { 

  cin >> n >> d >> m;
  int day;
  for(int i = 0; i<m; i++){
    cin >> day;
    vp.push_back(MP(day,i));
  }

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

  int l = 1, r = 1e12, mid, ans;

  while(l<=r){
    mid = l + (r-l)/2;
    if(check(mid)){
        ans = mid;
        r = mid - 1;
    }else{
        l = mid + 1;
    }
  }

  cout << ans << endl;

  make_ans(ans);

return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'void make_ans(int)':
jobs.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while(j < for_ans[i].size()){
      |               ~~^~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:91:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   91 |   int l = 1, r = 1e12, mid, ans;
      |                  ^~~~
jobs.cpp:105:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |   make_ans(ans);
      |   ~~~~~~~~^~~~~

• Subtask 1: 90 / 100