Submission #891177

#	Time	Username	Problem	Language	Result	Execution time	Memory
891177		Vedant_05	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	210 ms	20704 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define pb(a) push_back(a)
#define pbr(a,b) pb(make_pair(a,b))
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define F first
#define S second

ll M = 1e9 + 7;                 //998244353;
const int N = 100001;

ll binpow(ll a, ll b){    ll ans = 1;    while(b > 0){        if(b&1)     ans = (ans * a) % M;        a = (a*a) % M;        b >>= 1;    }    return ans;     }
bool sS(pi p1, pi p2){    return (p1.S < p2.S);     }
bool sF(pi p1, pi p2){    return (p1.F < p2.F);     }

bool chk(int mid, int n, int m, int d, queue<int> q, int a[]){
    fr(i, 1, n){
        fr(j, 0, mid-1){
            if(q.empty())
                break;
            int u = q.front();
            if(a[u] > i)
                break;
            q.pop();
            if(a[u]+d < i)
                return 0;
        }
    }
    if(q.empty())
        return 1;
    return 0;
}

void solve()
{
    int n, d, m;
    cin >> n >> d >> m;
    vector<vi> vec(n-d+1);
    int a[m+1];
    fr(i, 1, m){
        cin >> a[i];
        vec[a[i]].pb(i);
    }
    queue<int> q;
    fr(i, 1, n-d){
        for(auto u: vec[i])
            q.push(u);
    }
    int l = 0, r = m;
    while(r > l+1){
        // cout << l << " " << r << "\n";
        int mid = (l+r) / 2;
        if(chk(mid, n, m, d, q, a))
            r = mid;
        else
            l = mid;
        // cout << "\n";
    }
    
    cout << r << "\n";
    fr(i, 1, n){
        fr(j, 0, r-1){
            if(q.empty())
                break;
            int u = q.front();
            if(a[u] > i)
                continue;
            q.pop();
            cout << u << " ";
        }
        cout << "0\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    
    int t=1;
    // cin >> t;
    for(int i = 1; i <= t; i++)
    {
        // cout << "t: " << t << "\n";
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100