oj.uz

Submission #311700

# Submission time Handle Problem Language Result Execution time Memory
311700 2020-10-11T05:46:14 Z mohamedsobhi777 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 283 ms 13912 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1900 KB Output is correct
2 Correct 22 ms 1908 KB Output is correct
3 Correct 21 ms 1904 KB Output is correct
4 Correct 21 ms 1912 KB Output is correct
5 Correct 21 ms 1908 KB Output is correct
6 Correct 22 ms 1832 KB Output is correct
7 Correct 21 ms 2040 KB Output is correct
8 Correct 21 ms 1912 KB Output is correct
9 Correct 33 ms 2032 KB Output is correct
10 Correct 32 ms 2032 KB Output is correct
11 Correct 30 ms 1912 KB Output is correct
12 Correct 60 ms 3304 KB Output is correct
13 Correct 91 ms 4832 KB Output is correct
14 Correct 125 ms 6388 KB Output is correct
15 Correct 153 ms 7776 KB Output is correct
16 Correct 190 ms 9304 KB Output is correct
17 Correct 223 ms 10836 KB Output is correct
18 Correct 249 ms 12376 KB Output is correct
19 Correct 283 ms 13912 KB Output is correct
20 Correct 223 ms 10836 KB Output is correct