Submission #919792

#	Time	Username	Problem	Language	Result	Execution time	Memory
919792		Ahmed_Kaaniche	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	135 ms	18316 KiB

jobs

#include <bits/stdc++.h>
using namespace std;




#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define lob lower_bound
#define upb upper_bound
#define bin binary_search
#define endl "\n"
#define tos to_string

ll n,m,d;
vector<vector<ll>>arr;

bool val(ll x){
    int cnt1=0,cnt2=1;
    for (int i = 0; i < n-d; ++i) {
        cnt1=0;
        for(auto elt :arr[i]){
            if(cnt1<x){
                cnt1++;
                continue;
            }
            cnt2++;
        }
        if ((cnt2/x==d&&cnt2%x>0)||cnt2/x>d)
            return 0;
    }
    return 1;
}

int main() {
    //the booster of input and output :
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
//    freopen("perimeter.in","r",stdin);
//    freopen("perimeter.out","w",stdout);
    
    //the body :
    cin>>n>>d>>m;
    arr.resize(n-d);
    for (int i = 0; i < m; ++i) {
        int x;
        cin>> x;
        arr[--x].pb(i);
    }
    
    ll l=0,r=1e9,mid;
    while (l+1<r){
        mid=(l+r)/2;
        if(val(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    cout << r << endl;
    int cnt=0,j=0;
    for (int i = 0; i < n-d; ++i) {
        for(auto elt :arr[i]){
            cout << elt+1 << ' ';
            cnt++;
            if (cnt%r==0){
                cout << 0 << endl;
                j++;
            }
        }
    }
    
    for (int i = 0; i < n-j; ++i) {
        cout << 0 << endl;
    }
    
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool val(long long int)':
jobs.cpp:26:18: warning: unused variable 'elt' [-Wunused-variable]
   26 |         for(auto elt :arr[i]){
      |                  ^~~

• Subtask 1: 10 / 100