oj.uz

Submission #311698

# Submission time Handle Problem Language Result Execution time Memory
311698 2020-10-11T05:38:55 Z mohamedsobhi777 Job Scheduling (CEOI12_jobs) C++14
55 / 100
 378 ms 17364 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){
        for(int i = 0 ;i < m ;++ i){
                int mac = i / x + 1; 
                if(mac > n || mac > v[i].first + d)
                        return 0 ; 
        }
        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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 2132 KB Output isn't correct
2 Incorrect 31 ms 2140 KB Output isn't correct
3 Incorrect 33 ms 2156 KB Output isn't correct
4 Incorrect 33 ms 2160 KB Output isn't correct
5 Incorrect 33 ms 2288 KB Output isn't correct
6 Incorrect 31 ms 2160 KB Output isn't correct
7 Incorrect 32 ms 2160 KB Output isn't correct
8 Incorrect 30 ms 2168 KB Output isn't correct
9 Correct 41 ms 2288 KB Output is correct
10 Correct 42 ms 2292 KB Output is correct
11 Correct 38 ms 2296 KB Output is correct
12 Correct 86 ms 4072 KB Output is correct
13 Correct 121 ms 6040 KB Output is correct
14 Correct 165 ms 8288 KB Output is correct
15 Incorrect 200 ms 9696 KB Output isn't correct
16 Correct 244 ms 12224 KB Output is correct
17 Correct 286 ms 14164 KB Output is correct
18 Correct 335 ms 15320 KB Output is correct
19 Correct 378 ms 17364 KB Output is correct
20 Correct 290 ms 14164 KB Output is correct