Submission #441754

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441754	2021-07-06T03:43:38 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	325 ms	38092 KB

jobs

//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 1000005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, m, d;
ii a[N];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> d >> m;
    for(int i=1; i<=m; i++){
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a+1,a+1+m);
}

bool ok(int machine){
    int endT[machine] = {0};
    int cur=0;
    int delays = minf;
    for(int i=1; i<=m; i++){
        if (cur==machine) cur=0;
        if (endT[cur]+1 > a[i].first){
            endT[cur]++;
            delays = max(delays,endT[cur]-a[i].fi);
        }
        else endT[cur]=a[i].fi;
        cur++;
    }
    return delays <= d;
}

vector<int> res[100012];

void proc()
{
    int l = 0, r = m, ans;
    while (r >= l){
        int mid = (l+r)/2;
        if (ok(mid)){
            r = mid-1;
            ans=mid;
        }
        else l = mid+1;
    }
    cout << ans << endl;
    int endT[ans] = {0};
    for(int i=1, cur=0; i<=m; i++, cur++){
        if (cur==ans) cur=0;
        endT[cur]=max(a[i].fi,endT[cur]+1);
        res[endT[cur]].pb(a[i].se);
    }
    for(int i=1; i<=n; i++){
        for(int x : res[i]) cout << x << ' ';
        cout << 0 << '\n';
    }
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

jobs.cpp: In function 'void readfile()':
jobs.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6352 KB	Output is correct
2	Correct	26 ms	6320 KB	Output is correct
3	Correct	26 ms	6348 KB	Output is correct
4	Correct	26 ms	6332 KB	Output is correct
5	Correct	27 ms	6384 KB	Output is correct
6	Correct	26 ms	6456 KB	Output is correct
7	Correct	27 ms	6412 KB	Output is correct
8	Correct	26 ms	6364 KB	Output is correct
9	Correct	42 ms	6524 KB	Output is correct
10	Correct	44 ms	6472 KB	Output is correct
11	Correct	34 ms	6536 KB	Output is correct
12	Correct	70 ms	10776 KB	Output is correct
13	Correct	103 ms	15628 KB	Output is correct
14	Correct	145 ms	20164 KB	Output is correct
15	Correct	175 ms	21760 KB	Output is correct
16	Correct	214 ms	26500 KB	Output is correct
17	Runtime error	259 ms	34500 KB	Memory limit exceeded
18	Runtime error	288 ms	34992 KB	Memory limit exceeded
19	Runtime error	325 ms	38092 KB	Memory limit exceeded
20	Runtime error	262 ms	34428 KB	Memory limit exceeded