Submission #559623

#	Time	Username	Problem	Language	Result	Execution time	Memory
559623		srivatsav_kannan	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	342 ms	42872 KiB

jobs

#include <iostream>
#include <array>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#include <algorithm>
#include <numeric>
#include <stack>
#include <cstring>
#include <bitset>
#include <climits>
#include <valarray>
#include <list>
#define int long long int
#define inf 100000000000
#define endl '\n'
#define mod 998244353
using namespace std;
int n,m,d;
pair<int,int> ar[1000000];
vector<vector<int>> ans;
bool f(int mid){
    int day = 1;
    vector<int> today;
    int done_t = 0;
    for (int i = 0; i < d; i++){
        while (ar[i].first > day || done_t == mid){
            day++;
            done_t = 0;
            today.push_back(0);
            ans.push_back(today);
            today.clear();
        }
        
        if (day-ar[i].first > m || day > n) return false;
        today.push_back(ar[i].second);
        done_t++;
    }
    today.push_back(0);
    ans.push_back(today);
    return true;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("sabotage.in");
//    ofstream cout("sabotage.out");
    cin >> n >> m >> d;
    for (int i = 0; i < d; i++) {
        cin >> ar[i].first;
        ar[i].second = i+1;
    }
    vector<vector<int>> aans;
    sort(ar, ar+d);
    int lo = 1, hi = d;
    
    while (lo < hi) {
        ans.clear();
        int mid = (lo+hi)/2;
        if (f(mid)) {
            hi = mid;
            aans = ans;
        }
        else lo = mid+1;
    }
    cout << lo << endl;
    for (int i = 0; i < aans.size(); i++){
        for (int j = 0; j < aans[i].size(); j++){
            cout << aans[i][j] << " ";
        }
        cout << endl;
    }
    for (int i = 0; i < n-aans.size(); i++) cout << 0 << endl;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:71:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < aans.size(); i++){
      |                     ~~^~~~~~~~~~~~~
jobs.cpp:72:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 0; j < aans[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~
jobs.cpp:77:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   77 |     for (int i = 0; i < n-aans.size(); i++) cout << 0 << endl;
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100