Submission #891177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891177	2023-12-22T10:10:14 Z	Vedant_05	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	210 ms	20704 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2776 KB	Output is correct
2	Correct	16 ms	3036 KB	Output is correct
3	Correct	15 ms	2852 KB	Output is correct
4	Correct	16 ms	2776 KB	Output is correct
5	Correct	16 ms	2780 KB	Output is correct
6	Correct	16 ms	2780 KB	Output is correct
7	Correct	17 ms	2780 KB	Output is correct
8	Correct	18 ms	2776 KB	Output is correct
9	Correct	20 ms	4984 KB	Output is correct
10	Correct	20 ms	4940 KB	Output is correct
11	Correct	17 ms	2396 KB	Output is correct
12	Correct	39 ms	4300 KB	Output is correct
13	Correct	71 ms	7116 KB	Output is correct
14	Correct	85 ms	9368 KB	Output is correct
15	Correct	112 ms	10756 KB	Output is correct
16	Correct	164 ms	13872 KB	Output is correct
17	Correct	175 ms	16272 KB	Output is correct
18	Correct	187 ms	16916 KB	Output is correct
19	Correct	210 ms	20704 KB	Output is correct
20	Correct	160 ms	16416 KB	Output is correct