Submission #919794

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919794	2024-02-01T16:24:53 Z	Ahmed_Kaaniche	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	122 ms	18000 KB

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=0;
    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

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

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2004 KB	Output is correct
2	Correct	13 ms	2004 KB	Output is correct
3	Correct	14 ms	2004 KB	Output is correct
4	Correct	13 ms	2004 KB	Output is correct
5	Correct	14 ms	2260 KB	Output is correct
6	Correct	13 ms	2004 KB	Output is correct
7	Correct	14 ms	2004 KB	Output is correct
8	Correct	13 ms	2004 KB	Output is correct
9	Correct	27 ms	4688 KB	Output is correct
10	Correct	28 ms	4764 KB	Output is correct
11	Incorrect	13 ms	2136 KB	Output isn't correct
12	Incorrect	25 ms	3672 KB	Output isn't correct
13	Incorrect	37 ms	6736 KB	Output isn't correct
14	Incorrect	63 ms	8272 KB	Output isn't correct
15	Incorrect	66 ms	9808 KB	Output isn't correct
16	Incorrect	88 ms	12368 KB	Output isn't correct
17	Incorrect	103 ms	15376 KB	Output isn't correct
18	Incorrect	97 ms	14928 KB	Output isn't correct
19	Incorrect	122 ms	18000 KB	Output isn't correct
20	Incorrect	113 ms	15556 KB	Output isn't correct