Submission #939427

#	Time	Username	Problem	Language	Result	Execution time	Memory
939427		JakobZorz	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	258 ms	20656 KiB

jobs

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

int n,d,m;
vector<int>jobs[100000];

vector<vector<int>>get(int k){
    vector<vector<int>>res(n);
    queue<pair<int,int>>q;
    for(int i=0;i<n;i++){
        for(int j:jobs[i]){
            q.push({i+d,j});
        }
        
        if(q.size()&&q.front().first<i)
            return {};
        for(int j=0;j<k&&q.size();j++){
            res[i].push_back(q.front().second);
            q.pop();
        }
    }
    
    return res;
}

void solve(){
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int a;
        cin>>a;
        jobs[a-1].push_back(i);
    }
    
    int l=0,r=m;
    while(l<r-1){
        int mid=(l+r)/2;
        if(get(mid).empty()){
            l=mid;
        }else{
            r=mid;
        }
    }
    cout<<r<<"\n";
    auto res=get(r);
    for(auto i:res){
        for(auto j:i){
            cout<<j<<" ";
        }
        cout<<"0\n";
    }
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

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

• Subtask 1: 100 / 100