Submission #891174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891174	2023-12-22T10:00:31 Z	Vedant_05	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	171 ms	23520 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, queue<int> q, int a[]){
    fr(i, 1, n){
        fr(j, 0, mid-1){
            if(q.empty())
                break;
            int u = q.front();  q.pop();
            // cout << u << " " << a[u] << ' ' << i << " : ";
            if(a[u] < 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);
        a[i] += d;
    }
    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, 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();  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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	3036 KB	Output isn't correct
2	Incorrect	16 ms	3036 KB	Output isn't correct
3	Incorrect	16 ms	3036 KB	Output isn't correct
4	Incorrect	16 ms	3192 KB	Output isn't correct
5	Incorrect	14 ms	3036 KB	Output isn't correct
6	Incorrect	15 ms	3420 KB	Output isn't correct
7	Incorrect	15 ms	3036 KB	Output isn't correct
8	Incorrect	14 ms	3132 KB	Output isn't correct
9	Correct	21 ms	5408 KB	Output is correct
10	Correct	20 ms	5188 KB	Output is correct
11	Correct	19 ms	2896 KB	Output is correct
12	Correct	33 ms	5184 KB	Output is correct
13	Correct	51 ms	8052 KB	Output is correct
14	Correct	76 ms	11032 KB	Output is correct
15	Incorrect	84 ms	12304 KB	Output isn't correct
16	Correct	122 ms	16360 KB	Output is correct
17	Correct	138 ms	19296 KB	Output is correct
18	Correct	147 ms	19564 KB	Output is correct
19	Correct	171 ms	23520 KB	Output is correct
20	Correct	140 ms	19380 KB	Output is correct