제출 #1285555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285555		xnoel	Job Scheduling (CEOI12_jobs)	C++20	10 / 100	317 ms	21044 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
long long n,delay,m; 
map<long long,long long> mp;
vector<pair<long long,long long>> vp;

bool alg(long long x){
    if (n*x<m) return false;
    long long preday=0,leftover=0;
    for (auto [day,count]: mp){
        leftover= max(leftover+(day-preday-1)*x,0LL);
        leftover+=max(count-x,0LL);
        if (leftover>x*delay) return false;
        preday=day;
    }
    if (preday+(leftover+x-1)/x>n) return false;
    return true;
}

int main(){
    //freopen("1.in","r",stdin);  
    cin>>n>>delay>>m;

    for (long long i=0;i<m;i++) {
        long long day;
        cin>>day;
        mp[day]++;
        vp.push_back({day,i+1});
    }
    sort(vp.begin(),vp.end());

    // for (auto x: mp) cout<<x.first<<" "<<x.second<<"\n";
    // cout<<"\n";

    long long low=1,high=m;
    while (low<high){
        long long mid=(low+high)/2;
        if (alg(mid)) high=mid;
        else low=mid+1;
    }
    cout<<low<<"\n";
    for (long long i=0;i<n;i++){
        for (long long j=0;j<low;j++){
            long long idx=i*low+j;
            if (idx>=m) {
                break;
            }
            cout<<vp[idx].second<<" ";
        }
        cout<<"0\n";
    }
}

• Subtask 1: 10 / 100