Submission #53855

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53855	2018-07-01T11:23:48 Z	SpeedOfMagic	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	388 ms	78000 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;
    int p = 1;
    int leftToFinish = 0;
    rep(r, 1, n + 1) {
        while (l + d < r) {
            p++;

            r--;

            int pointer = l;

            while (l <= r && pointer <= r) {
                while (l <= r && leftToFinish == 0) {
                    l++;
                    leftToFinish = sz(a[l]);
                }

                pointer = max(pointer, l);

                if (pointer > r)
                    break;

                int z = min(r - pointer + 1, leftToFinish);
                leftToFinish -= z;
                pointer += z;
            }

            while (l <= r && leftToFinish == 0) {
                l++;
                leftToFinish = sz(a[l]);
            }

            r++;
        }

        if (r == n)
            break;

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

            if (canDo == 0 || l > r)
                break;

            int z = min(canDo, leftToFinish);
            canDo -= z;
            leftToFinish -= z;
        }
    }

    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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	8056 KB	Output is correct
2	Correct	47 ms	8180 KB	Output is correct
3	Correct	40 ms	8180 KB	Output is correct
4	Correct	40 ms	8296 KB	Output is correct
5	Correct	41 ms	8364 KB	Output is correct
6	Correct	38 ms	8364 KB	Output is correct
7	Correct	47 ms	8364 KB	Output is correct
8	Correct	40 ms	8364 KB	Output is correct
9	Incorrect	225 ms	69200 KB	Output isn't correct
10	Incorrect	243 ms	69200 KB	Output isn't correct
11	Incorrect	24 ms	69200 KB	Output isn't correct
12	Incorrect	41 ms	69200 KB	Output isn't correct
13	Incorrect	61 ms	69200 KB	Output isn't correct
14	Incorrect	113 ms	69200 KB	Output isn't correct
15	Incorrect	107 ms	69200 KB	Output isn't correct
16	Incorrect	167 ms	69200 KB	Output isn't correct
17	Incorrect	205 ms	69200 KB	Output isn't correct
18	Incorrect	178 ms	69200 KB	Output isn't correct
19	Incorrect	388 ms	78000 KB	Output isn't correct
20	Incorrect	187 ms	78000 KB	Output isn't correct