oj.uz

Submission #850302

# Submission time Handle Problem Language Result Execution time Memory
850302 2023-09-16T09:49:03 Z srivatsav_kannan Job Scheduling (CEOI12_jobs) C++14
85 / 100
 255 ms 38848 KB 
#include <iostream>
#include <iomanip>
#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>
#include <unordered_map>
#include <unordered_set>
#include <complex>
//#include <bits/stdc++.h>
#define int long long int
#define double long double
#define endl '\n'
#define mod 1000000007
#define inf 2000000000000000000
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree < int ,  null_type ,  less ,  rb_tree_tag ,  tree_order_statistics_node_update>
const int mxm = 1000001;
pair<int,int> ar[mxm];
int n,d,m;
vector<int> ans[100001];
bool f(int mid){
    for (int i = 1; i <= n; i++) ans[i].clear();
    int day = 1;
    int used = 0;
    for (int i = 0; i < m; i++){
        if (day > n) return false;
        used++;
        day = max(day, ar[i].first);
        ans[day].push_back(ar[i].second);
        if (day-ar[i].first > d || day > n) return false;
        if (used == mid) {
            used = 0;
            day++;
        }
    }
    return true;
}

void solve(){
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> ar[i].first;
        ar[i].second = i+1;
    }
    sort(ar, ar+m);

    int l = 1, r = m;
    while (l < r) {
        int mid = (l+r)/2;
        if (f(mid)) r = mid;
        else l = mid+1;
    }
    cout << l << endl;
    f(l);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < ans[i].size(); j++){
            cout << ans[i][j] << " ";
        }
        cout << 0 << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//       freopen("swap.in", "r", stdin);
//       freopen("swap.out", "w", stdout);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:70: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]
   70 |         for (int j = 0; j < ans[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6240 KB Output is correct
2 Correct 18 ms 6240 KB Output is correct
3 Correct 18 ms 6240 KB Output is correct
4 Correct 18 ms 6228 KB Output is correct
5 Correct 18 ms 6236 KB Output is correct
6 Correct 18 ms 6240 KB Output is correct
7 Correct 19 ms 6240 KB Output is correct
8 Correct 18 ms 6240 KB Output is correct
9 Correct 30 ms 6740 KB Output is correct
10 Correct 31 ms 6488 KB Output is correct
11 Correct 27 ms 7184 KB Output is correct
12 Correct 52 ms 11616 KB Output is correct
13 Correct 79 ms 15952 KB Output is correct
14 Correct 108 ms 20560 KB Output is correct
15 Incorrect 131 ms 22664 KB Output isn't correct
16 Correct 165 ms 27928 KB Output is correct
17 Correct 198 ms 31312 KB Output is correct
18 Runtime error 216 ms 37000 KB Memory limit exceeded
19 Runtime error 255 ms 38848 KB Memory limit exceeded
20 Correct 200 ms 31316 KB Output is correct