oj.uz

답안 #53817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53817 2018-07-01T08:51:37 Z SpeedOfMagic Job Scheduling (CEOI12_jobs) C++17
10 / 100
 427 ms 85080 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, 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

# 결과 실행 시간 메모리 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)