oj.uz

Submission #453170

# Submission time Handle Problem Language Result Execution time Memory
453170 2021-08-04T08:29:14 Z BT21tata Job Scheduling (CEOI12_jobs) C++17
20 / 100
 1000 ms 14312 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 pos=0;
    for(int day=1; day<=n; day++)
    {
        for(int i=0; i<x and pos<m; i++)
        {
            if(a[pos].F<=day and a[pos].F+d>=day) pos++;
            //cout<<x<<' '<<day<<' '<<a[pos].F<<' '<<pos<<endl;
        }
    }
    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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 1868 KB Time limit exceeded
2 Execution timed out 1081 ms 1868 KB Time limit exceeded
3 Execution timed out 1087 ms 1868 KB Time limit exceeded
4 Execution timed out 1092 ms 1824 KB Time limit exceeded
5 Execution timed out 1091 ms 1868 KB Time limit exceeded
6 Execution timed out 1084 ms 1768 KB Time limit exceeded
7 Execution timed out 1089 ms 1868 KB Time limit exceeded
8 Execution timed out 1091 ms 1868 KB Time limit exceeded
9 Execution timed out 1097 ms 1788 KB Time limit exceeded
10 Execution timed out 1081 ms 1868 KB Time limit exceeded
11 Correct 180 ms 2376 KB Output is correct
12 Correct 341 ms 4708 KB Output is correct
13 Correct 549 ms 6920 KB Output is correct
14 Execution timed out 1086 ms 6476 KB Time limit exceeded
15 Correct 934 ms 11452 KB Output is correct
16 Execution timed out 1096 ms 9668 KB Time limit exceeded
17 Execution timed out 1085 ms 11204 KB Time limit exceeded
18 Execution timed out 1095 ms 12740 KB Time limit exceeded
19 Execution timed out 1080 ms 14312 KB Time limit exceeded
20 Execution timed out 1082 ms 11204 KB Time limit exceeded