oj.uz

Submission #453180

# Submission time Handle Problem Language Result Execution time Memory
453180 2021-08-04T08:37:33 Z BT21tata Job Scheduling (CEOI12_jobs) C++17
100 / 100
 335 ms 20788 KB 
#include<bits/stdc++.h>
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
using namespace std;
const ll MOD=1e9+7;
//mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

ll n, d, m;
pll a[1000005];

bool check(ll x)
{
    int day=1, wtdy=0, pos=0;
    while(pos<m and day<=n)
    {
        if(a[pos].F<=day and day<=a[pos].F+d) wtdy++, pos++;
        else day++, wtdy=0;
        if(wtdy>=x) day++, wtdy=0;
    }
    if(pos==m) return 1;
    return 0;
}

int main()
{
    SPEED;
    cin>>n>>d>>m;
    for(int i=0; i<m; i++)
    {
        cin>>a[i].F;
        a[i].S=i+1;
    }
    sort(a, a+m);
    ll l=1, r=m, mid, pos=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
    for(int i=0; i<n; i++, cout<<0<<endl)
        for(int j=0; j<l and pos<m; j++)
            cout<<a[pos++].S<<' ';

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2380 KB Output is correct
2 Correct 24 ms 2404 KB Output is correct
3 Correct 24 ms 2380 KB Output is correct
4 Correct 27 ms 2456 KB Output is correct
5 Correct 24 ms 2372 KB Output is correct
6 Correct 24 ms 2400 KB Output is correct
7 Correct 24 ms 2416 KB Output is correct
8 Correct 24 ms 2400 KB Output is correct
9 Correct 41 ms 2628 KB Output is correct
10 Correct 49 ms 2648 KB Output is correct
11 Correct 38 ms 2376 KB Output is correct
12 Correct 67 ms 4708 KB Output is correct
13 Correct 103 ms 6980 KB Output is correct
14 Correct 171 ms 9168 KB Output is correct
15 Correct 176 ms 11508 KB Output is correct
16 Correct 222 ms 13884 KB Output is correct
17 Correct 292 ms 15996 KB Output is correct
18 Correct 285 ms 18320 KB Output is correct
19 Correct 335 ms 20788 KB Output is correct
20 Correct 262 ms 16056 KB Output is correct