Submission #1308592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308592		joze_plocnik	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	389 ms	31104 KiB

jobs

#include <iostream>
#include <string>
#include <algorithm> 
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype> // doda isupper 

#define int long long // vse ti je long long
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define forn(i,n) for(int i = 0; i<n; i++)
#define forn1(i,n) for(int i = 1; i<=n; i++)
#define all(x) (x).begin(), (x).end()
#define pi pair<int,int>
#define vvi vector<vi>
#define vvc vector<vector<char>>
#define sz(x) (x).size()
#define pb push_back
#define str string

using namespace std;

int n,m,d;
vpii stranke;

vvi urnik(int meja){
    vvi ans(n);
    int req_num = 0;

    for(int dan = 1; dan<=n; dan++){
        forn(i,meja){

            if(stranke[req_num].first > dan) break; // preveč naprej smo

            if(dan - stranke[req_num].first > d) return {}; //ne gre
            else{
                ans[dan-1].push_back(stranke[req_num++].second+1);
            }
            
            if(req_num == m) return ans;
        }
    }
    return {};
}

signed main() {
    cin >> n >> d>> m;
    stranke.resize(m); //kdaj + id
    forn(i,m){
        cin >> stranke[i].first; //stranke[i].first; 
        stranke[i].second = i;
    }   
    sort(all(stranke));
    int l = 1, r = m;
    while(l<r){
        int rob = (l+r)/2;
        //cout << rob << "\n";
        if(urnik(rob).empty()){
            l = rob+1;
        } else {
            r = rob;
        }
    }
    cout << l << "\n";
    vvi ans = urnik(l);
    forn(i,n){
        for(int nekaj : ans[i]) cout << nekaj << " ";
        cout <<"0\n";
    }



    return 0;
}

• Subtask 1: 100 / 100