oj.uz

답안 #370861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370861 2021-02-24T19:53:25 Z Sorting 앵무새 (IOI11_parrots) C++17
100 / 100
 295 ms 237948 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int H = 320 + 256 + 3;
const int SZ = 90;

struct Big_Number{
    int a[SZ];

    void init(){ fill(a, a + SZ, 0); }
    Big_Number(){ init(); }

    friend Big_Number operator+(const Big_Number &l, const Big_Number &r){
        int add = 0;
        Big_Number ret;
        for(int i = SZ - 1; i >= 0; --i){
            int sum = l.a[i] + r.a[i] + add;
            ret.a[i] = sum % 256;
            add = sum / 256;
        }
        return ret;
    }

    friend bool operator<(const Big_Number &l, const Big_Number &r){
        for(int i = 0; i < SZ; ++i)
            if(l.a[i] != r.a[i])
                return l.a[i] < r.a[i];
        return false;
    }
};

static bool done = false;
static Big_Number bc[H][H];

static void output_number(Big_Number bn){
    bool start = false;
    for(int i = 0; i < SZ; ++i){
        if(bn.a[i]) start = true;
        if(start) cout << bn.a[i] << " ";
    }
    cout << endl;
}

void encode(int n, int m[]){
    if(!done){
        bc[0][0].a[SZ - 1] = 1;
        for(int i = 0; i < H; ++i){
            bc[i][0].a[SZ - 1] = 1;
            for(int j = 1; j <= i; ++j)
                bc[i][j] = bc[i - 1][j] + bc[i - 1][j - 1];
        }
        done = true;
    }

    int t = 5 * n, num = 255;
    Big_Number curr, add;
    for(int i = 0; i < n; ++i)
        curr.a[SZ - 1 - i] = m[i];
    for(; t > 0; --t){
        while(num && curr < bc[t + num - 1][t] + add) num--;
        send(num);
        add = add + bc[t + num - 1][t];
    }
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int H = 320 + 256 + 3;
const int SZ = 90;

struct Big_Number{
    int a[SZ];

    void init(){ fill(a, a + SZ, 0); }
    Big_Number(){ init(); }

    friend Big_Number operator+(const Big_Number &l, const Big_Number &r){
        int add = 0;
        Big_Number ret;
        for(int i = SZ - 1; i >= 0; --i){
            int sum = l.a[i] + r.a[i] + add;
            ret.a[i] = sum % 256;
            add = sum / 256;
        }
        return ret;
    }

    friend bool operator<(const Big_Number &l, const Big_Number &r){
        for(int i = 0; i < SZ; ++i)
            if(l.a[i] != r.a[i])
                return l.a[i] < r.a[i];
        return false;
    }
};

static bool done = false;
static Big_Number bc[H][H];

void decode(int n, int l, int x[]){
    if(!done){
        bc[0][0].a[SZ - 1] = 1;
        for(int i = 0; i < H; ++i){
            bc[i][0].a[SZ - 1] = 1;
            for(int j = 1; j <= i; ++j)
                bc[i][j] = bc[i - 1][j] + bc[i - 1][j - 1];
        }
        done = true;
    }

    sort(x, x + l);

    int t = 5 * n, num = 255;
    Big_Number curr;
    for(; t > 0; --t){
        int num = x[t - 1];
        curr = curr + bc[t + num - 1][t];
    }

    for(int i = 0; i < n; ++i)
        output(curr.a[SZ - 1 - i]);
}

Compilation message

encoder.cpp:38:13: warning: 'void output_number(Big_Number)' defined but not used [-Wunused-function]
   38 | static void output_number(Big_Number bn){
      |             ^~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:51:20: warning: unused variable 'num' [-Wunused-variable]
   51 |     int t = 5 * n, num = 255;
      |                    ^~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 237096 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 267 ms 237292 KB Output is correct
2 Correct 286 ms 237552 KB Output is correct
3 Correct 270 ms 237432 KB Output is correct
4 Correct 275 ms 237536 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 237488 KB Output is correct
2 Correct 290 ms 237672 KB Output is correct
3 Correct 275 ms 237892 KB Output is correct
4 Correct 281 ms 237748 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 237376 KB Output is correct
2 Correct 278 ms 237692 KB Output is correct
3 Correct 274 ms 237688 KB Output is correct
4 Correct 278 ms 237668 KB Output is correct
5 Correct 283 ms 237616 KB Output is correct
6 Correct 276 ms 237540 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 237664 KB Output is correct - P = 5.000000
2 Correct 277 ms 237596 KB Output is correct - P = 5.000000
3 Correct 284 ms 237652 KB Output is correct - P = 5.000000
4 Correct 285 ms 237464 KB Output is correct - P = 5.000000
5 Correct 295 ms 237600 KB Output is correct - P = 5.000000
6 Correct 294 ms 237612 KB Output is correct - P = 5.000000
7 Correct 293 ms 237948 KB Output is correct - P = 5.000000