Submission #699675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
699675	2023-02-17T17:22:22 Z	edev1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	476 ms	20412 KB

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;
            placed = 0;
            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 = 1e7, 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

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:106:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |   make_ans(ans);
      |   ~~~~~~~~^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	4860 KB	Output is correct
2	Correct	44 ms	4900 KB	Output is correct
3	Correct	46 ms	4976 KB	Output is correct
4	Correct	42 ms	4964 KB	Output is correct
5	Correct	42 ms	4848 KB	Output is correct
6	Correct	42 ms	4980 KB	Output is correct
7	Correct	43 ms	4928 KB	Output is correct
8	Correct	45 ms	4976 KB	Output is correct
9	Correct	148 ms	5028 KB	Output is correct
10	Correct	152 ms	5024 KB	Output is correct
11	Correct	44 ms	4736 KB	Output is correct
12	Correct	90 ms	6956 KB	Output is correct
13	Correct	122 ms	9268 KB	Output is correct
14	Correct	185 ms	11464 KB	Output is correct
15	Correct	200 ms	12364 KB	Output is correct
16	Correct	277 ms	14324 KB	Output is correct
17	Correct	316 ms	18372 KB	Output is correct
18	Correct	335 ms	18732 KB	Output is correct
19	Correct	476 ms	20412 KB	Output is correct
20	Correct	316 ms	18324 KB	Output is correct