제출 #541408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541408		omohamadooo	Job Scheduling (CEOI12_jobs)	C++14	20 / 100	1008 ms	52580 KiB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7;
const int  N=5e5 + 7 ;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po1(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll n , m ,d;
vector<ll>v[N];
vector<ll>ans[N];
priority_queue<pii,vector<pii>,greater<pii>>q;

bool ok(ll x)
{
    while(q.size()) q.pop();
    for(ll i= 1; i <= n ; i ++) ans[i].clear();
    for(ll i= 1; i <= n ; i++){
        for(auto j : v[i]) q.push({i, j});
        if(q.size() && i - q.top().F > d ) return 0;
        ll f = x;
        while(f -- && q.size()){
            ans[i].pb(q.top().S);
            q.pop();
        }
    }
    return 1;
}

void solve()
{
    cin >> n >> d >> m;
    for(ll i= 1; i <= m ; i ++){
        ll x;
        cin >> x;
        v[x].pb(i);
    }
    ll l = 1 , r = n , mid;
    while(l < r){
        mid = (l + r)/2;
        if(ok(mid)) r = mid;
        else l = mid + 1;
    }
    ok(l);
    cout << l << endl;
    for(ll i= 1; i <= n ; i++){
        for(auto j : ans[i]) cout << j << ' ';
        cout << 0 << endl;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

• Subtask 1: 20 / 100