Submission #818373

#	Time	Username	Problem	Language	Result	Execution time	Memory
818373		trMatherz	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	379 ms	17928 KiB

jobs

      #include <iostream>

/*
#include <fstream>
std::ifstream cin ("shuffle.in");
std::ofstream cout ("shuffle.out");
*/

using namespace std;

#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <list>
#include <numeric>
#include <cmath>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()



#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vpi vector<pair<int,int>>
#define vb vector<bool>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>

#define FR(x, a, b) for(int x = a; x < b; x++)
#define F(x, b) FR(x, 0, b)


#define f first
#define s second
#define ll long long

using namespace std;

/*
 8 2 12
 1 2 4 2 1 3 5 6 2 3 6 4
 */

int main(){
    int n, k, m; cin >> n >> k >> m;
    vi a(n); vpi p(m);
    F(i, m){cin >> p[i].f; p[i].f--; a[p[i].f]++; p[i].s = i + 1;}
    sort(all(p));
    auto check = [&](int x){
        int d = 0, dead = 0;
        while(d < n){
            int dl = x;
           
            while(dl > 0 && d < n){
                while(a[d] == 0 && d < n){d++;}
                int amt = min(a[d], dl);
                a[d] -= amt;
                dl -= amt;
            }
            while(a[d] == 0 && d < n){d++;}
            dead++;
            if(dead - d > k){ return false;}
        }
       
        return true;
    };
    
    int l = 1, r = 1e6;
    
    
    while(l < r){
        int mi = (r + l)/2;
        auto t = a;
        
        if(check(mi)){
            r = mi;
        } else {
            l = mi + 1;
        }
        a = t;
    }
   
    cout << l << endl;
    int po = 0;
    F(i, n){
        int c = l;
        while(c > 0 && po < m){
            cout << p[po].s << " ";
            c--;
            po++;
        }
        
        
        
        cout << 0 << endl;
    }
    
    return 0;
}

• Subtask 1: 55 / 100