oj.uz

Submission #850277

# Submission time Handle Problem Language Result Execution time Memory
850277 2023-09-16T09:20:17 Z srivatsav_kannan Job Scheduling (CEOI12_jobs) C++14
0 / 100
 240 ms 38220 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 ff(int mid){
    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;
    }
}
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;
    ff(l);
}

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 18 ms 4880 KB Expected EOLN
2 Incorrect 19 ms 4852 KB Expected EOLN
3 Incorrect 18 ms 4704 KB Expected EOLN
4 Incorrect 21 ms 4972 KB Expected EOLN
5 Incorrect 16 ms 4828 KB Expected EOLN
6 Incorrect 20 ms 4836 KB Expected EOLN
7 Incorrect 17 ms 4704 KB Expected EOLN
8 Incorrect 17 ms 4792 KB Expected EOLN
9 Incorrect 34 ms 10080 KB Expected EOLN
10 Incorrect 35 ms 10144 KB Expected EOLN
11 Incorrect 22 ms 4664 KB Expected EOLN
12 Incorrect 47 ms 8568 KB Expected EOLN
13 Incorrect 68 ms 13804 KB Expected EOLN
14 Incorrect 104 ms 16672 KB Expected EOLN
15 Incorrect 114 ms 21164 KB Output isn't correct
16 Incorrect 141 ms 23016 KB Expected EOLN
17 Incorrect 170 ms 31380 KB Expected EOLN
18 Incorrect 196 ms 32144 KB Expected EOLN
19 Runtime error 240 ms 38220 KB Memory limit exceeded
20 Incorrect 177 ms 31340 KB Expected EOLN