Submission #699634

#	Time	Username	Problem	Language	Result	Execution time	Memory
699634		edev1	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	3 ms	4988 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 (200001);

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() { 
 
 #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt", "w", stdout); 
 #endif

  //code here

  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 (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:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen("input.txt","r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:85:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    freopen("output.txt", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:114:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |   make_ans(ans);
      |   ~~~~~~~~^~~~~

• Subtask 1: 0 / 100