Submission #53817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53817	2018-07-01T08:51:37 Z	SpeedOfMagic	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	427 ms	85080 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 leftToDo[n];
        rep(i, 1, n)
            leftToDo[i] = sz(a[i]);

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

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

                int z = min(canDo, leftToDo[ll]);
                canDo -= z;
                leftToDo[ll] -= z;
            }

            if (ll + d < rr) {
                l = p;
                goto nxt;
            }
        }
        r = p;
        nxt:;
    }

    put r;
    eol;

    int canDo = 0;
    int ll = 1;
    rep(rr, 1, n) {
        canDo += r;
        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

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	38 ms	8184 KB	Output isn't correct
2	Incorrect	48 ms	8200 KB	Output isn't correct
3	Incorrect	45 ms	8292 KB	Output isn't correct
4	Incorrect	47 ms	8332 KB	Output isn't correct
5	Incorrect	41 ms	8420 KB	Output isn't correct
6	Incorrect	55 ms	8420 KB	Output isn't correct
7	Incorrect	58 ms	8420 KB	Output isn't correct
8	Incorrect	41 ms	8420 KB	Output isn't correct
9	Incorrect	284 ms	69420 KB	Output isn't correct
10	Incorrect	242 ms	69628 KB	Output isn't correct
11	Incorrect	22 ms	69628 KB	Output isn't correct
12	Correct	42 ms	69628 KB	Output is correct
13	Incorrect	60 ms	69628 KB	Output isn't correct
14	Correct	118 ms	69628 KB	Output is correct
15	Incorrect	105 ms	69628 KB	Output isn't correct
16	Runtime error	151 ms	69628 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	166 ms	69628 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Incorrect	238 ms	69628 KB	Output isn't correct
19	Incorrect	427 ms	85080 KB	Output isn't correct
20	Runtime error	156 ms	85080 KB	Execution killed with signal 11 (could be triggered by violating memory limits)