답안 #53856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53856 2018-07-01T11:32:11 Z SpeedOfMagic Job Scheduling (CEOI12_jobs) C++17
40 / 100
452 ms 77872 KB
/** 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;}
# 결과 실행 시간 메모리 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