Submission #53856

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53856	2018-07-01T11:32:11 Z	SpeedOfMagic	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	452 ms	77872 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 && l != 0) {
            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	40 ms	8060 KB	Output is correct
2	Correct	40 ms	8184 KB	Output is correct
3	Correct	42 ms	8240 KB	Output is correct
4	Correct	40 ms	8240 KB	Output is correct
5	Correct	38 ms	8324 KB	Output is correct
6	Correct	43 ms	8324 KB	Output is correct
7	Correct	42 ms	8324 KB	Output is correct
8	Correct	55 ms	8324 KB	Output is correct
9	Incorrect	262 ms	69068 KB	Output isn't correct
10	Incorrect	240 ms	69072 KB	Output isn't correct
11	Incorrect	28 ms	69072 KB	Output isn't correct
12	Incorrect	40 ms	69072 KB	Output isn't correct
13	Incorrect	61 ms	69072 KB	Output isn't correct
14	Incorrect	123 ms	69072 KB	Output isn't correct
15	Incorrect	101 ms	69072 KB	Output isn't correct
16	Incorrect	327 ms	69072 KB	Output isn't correct
17	Incorrect	205 ms	69072 KB	Output isn't correct
18	Incorrect	191 ms	69072 KB	Output isn't correct
19	Incorrect	452 ms	77872 KB	Output isn't correct
20	Incorrect	209 ms	77872 KB	Output isn't correct