oj.uz

Submission #850294

# Submission time Handle Problem Language Result Execution time Memory
850294 2023-09-16T09:36:56 Z srivatsav_kannan Job Scheduling (CEOI12_jobs) C++17
0 / 100
 210 ms 34920 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;
bool f(int mid){
    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);
        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;
    int mid = l;
    int day = 1;
    int used = 0;
    vector<int> ans[n+1];
    vector<int> cur;

    for (int i = 0; i < m; i++){
        used++;
        day = max(day, ar[i].first);
        ans[day].push_back(ar[i].second);
        if (used == mid) {
            used = 0;
            day++;
        }
    }
    for (int i = 1; i <= n; i++){
        ans[i].push_back(0);
        for (int j:ans[i]){
            cout << j << " ";
        }
        cout << 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;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4488 KB Expected EOLN
2 Incorrect 15 ms 4448 KB Expected EOLN
3 Incorrect 16 ms 4488 KB Expected EOLN
4 Incorrect 15 ms 4444 KB Expected EOLN
5 Incorrect 15 ms 4448 KB Expected EOLN
6 Incorrect 15 ms 4448 KB Expected EOLN
7 Incorrect 15 ms 4448 KB Expected EOLN
8 Incorrect 18 ms 4448 KB Expected EOLN
9 Incorrect 38 ms 9812 KB Expected EOLN
10 Incorrect 33 ms 9816 KB Expected EOLN
11 Incorrect 21 ms 4188 KB Expected EOLN
12 Incorrect 44 ms 7956 KB Expected EOLN
13 Incorrect 70 ms 12628 KB Expected EOLN
14 Incorrect 91 ms 14672 KB Expected EOLN
15 Incorrect 108 ms 19280 KB Output isn't correct
16 Incorrect 134 ms 20192 KB Expected EOLN
17 Incorrect 185 ms 27972 KB Expected EOLN
18 Incorrect 189 ms 29060 KB Expected EOLN
19 Runtime error 210 ms 34920 KB Memory limit exceeded
20 Incorrect 159 ms 27984 KB Expected EOLN