Submission #53858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53858	2018-07-01T12:04:33 Z	SpeedOfMagic	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	395 ms	77800 KB

jobs

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
//#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here

void run() {
    int n, d, m;
    read(n, d, m);
    n++;

    queue<int> a[n];

    rep(i, 0, m) {
        int k;
        get k;
        a[k].push(i + 1);
    }

    int l = 0, r = m + 1;

    while (l + 1 < r) {
        int p = (l + r) / 2;
        int ll = 1;
        int leftToFinish = sz(a[ll]);

        rep(rr, 1, n + 1) {
            if (ll + d < rr) {
                l = p;
                goto nxt;
            }

            if (rr == n)
                break;

            int canDo = p;
            while(ll <= rr) {
                while (ll <= rr && leftToFinish == 0) {
                    ll++;
                    leftToFinish = sz(a[ll]);
                }

                if (canDo == 0 || ll > rr)
                    break;

                int z = min(canDo, leftToFinish);
                canDo -= z;
                leftToFinish -= z;
            }
        }
        r = p;
        nxt:;
    }

    int p = r;
    put p;
    eol;

    int ll = 1;
    rep(rr, 1, n) {
        int canDo = p;
        while(ll <= rr) {
            while (ll <= rr && a[ll].empty())
                ll++;

            if (canDo == 0 || ll > rr)
                break;

            int z = min(canDo, sz(a[ll]));
            canDo -= z;
            while(z) {
                print(a[ll].front());
                a[ll].pop();
                z--;
            }
        }
        put 0;
        eol;
    }
}

int32_t main() {srand(time(0));ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);put setprecision(15);run();return 0;}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	8056 KB	Output is correct
2	Correct	38 ms	8056 KB	Output is correct
3	Correct	44 ms	8216 KB	Output is correct
4	Correct	38 ms	8308 KB	Output is correct
5	Correct	40 ms	8308 KB	Output is correct
6	Correct	44 ms	8316 KB	Output is correct
7	Correct	64 ms	8380 KB	Output is correct
8	Correct	63 ms	8380 KB	Output is correct
9	Correct	242 ms	69188 KB	Output is correct
10	Correct	231 ms	69188 KB	Output is correct
11	Correct	23 ms	69188 KB	Output is correct
12	Correct	39 ms	69188 KB	Output is correct
13	Correct	65 ms	69188 KB	Output is correct
14	Correct	112 ms	69188 KB	Output is correct
15	Correct	100 ms	69188 KB	Output is correct
16	Correct	159 ms	69188 KB	Output is correct
17	Correct	189 ms	69188 KB	Output is correct
18	Correct	214 ms	69188 KB	Output is correct
19	Correct	395 ms	77800 KB	Output is correct
20	Correct	189 ms	77800 KB	Output is correct