Submission #311700

#	Time	Username	Problem	Language	Result	Execution time	Memory
311700		mohamedsobhi777	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	283 ms	13912 KiB

jobs

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e6 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n,d , m; 
vector<pair<int,int> > v ; 

bool check(int x){
        int k = 0 ;
        for(int i = 1 ;i <= n ; ++ i){
                for(int j = 0 ;j < x && k < m; ++ j){
                        if(i > v[k].first + d)
                                return 0 ; 
                        if(i>=v[k].first){
                                k ++ ; 
                        }else break ; 
                }
        }
        return 1; 
}

void answer(int x){

        int k = 0 ; 
        for(int i = 0 ;i < n ; ++ i){
                for(int j = 0 ;j < x && k < m ; ++ j){
                        cout<< v[k++].second + 1 <<" " ; 
                }
                cout<<"0\n" ; 
        }
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n >> d >> m ;

        for(int i = 0 ;i < m ; ++ i){
                int x ;
                cin >> x ;
                v.push_back({x , i}) ; 
        }       

        sort(v.begin() , v.end()) ; 

        int l = 1 , r = m ;
        int ans = m ; 
        while(l<=r){
                int mid = (l+r) >> 1; 
                if(check(mid)){
                        ans = mid ;
                        r = mid - 1; 
                }
                else l = mid + 1; 
        } 
        cout<<ans <<"\n" ; 
        answer(ans) ; 
        return 0 ; 
}


/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

• Subtask 1: 100 / 100