Submission #828744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828744	2023-08-17T14:55:34 Z	bachhoangxuan	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	196 ms	26800 KB

jobs

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
//#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
//const int inf=1e18;
const int mod=998244353;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=1000005;
const int maxq=1000005;
const int maxl=20;
const int maxa=1000000;
const int root=3;
/*
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
*/
const int base=101;

vector<int> cnt[maxn],cc[maxn];
int a[maxm];

void solve(){
    int n,d,m;cin >> n >> d >> m;
    for(int i=1;i<=m;i++){cin >> a[i];cnt[a[i]].push_back(i);}
    auto check = [&](int mid,int t=0){
        queue<int> q;
        for(int i=1;i<=n;i++){
            for(int x:cnt[i]) q.push(x);
            for(int j=0;j<mid;j++){
                if(q.empty()) break;
                int x=q.front();q.pop();
                if(a[x]<i-d) return false;
                if(t) cc[i].push_back(x);
            }
        }
        return true;
    };
    int l=1,r=m,res=m;
    while(r>=l){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }
    check(res,1);
    cout << res << '\n';
    for(int i=1;i<=n;i++){
        for(int x:cc[i]) cout << x << ' ';
        cout << 0 << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	7700 KB	Output is correct
2	Correct	27 ms	7692 KB	Output is correct
3	Correct	19 ms	7756 KB	Output is correct
4	Correct	24 ms	7744 KB	Output is correct
5	Correct	18 ms	7764 KB	Output is correct
6	Correct	19 ms	7756 KB	Output is correct
7	Correct	20 ms	7728 KB	Output is correct
8	Correct	20 ms	7692 KB	Output is correct
9	Correct	28 ms	7500 KB	Output is correct
10	Correct	29 ms	7548 KB	Output is correct
11	Correct	20 ms	7380 KB	Output is correct
12	Correct	45 ms	9892 KB	Output is correct
13	Correct	79 ms	13524 KB	Output is correct
14	Correct	101 ms	16516 KB	Output is correct
15	Correct	96 ms	17052 KB	Output is correct
16	Correct	136 ms	20600 KB	Output is correct
17	Correct	187 ms	26132 KB	Output is correct
18	Correct	196 ms	25296 KB	Output is correct
19	Correct	196 ms	26800 KB	Output is correct
20	Correct	179 ms	26112 KB	Output is correct