oj.uz

Submission #370862

# Submission time Handle Problem Language Result Execution time Memory
370862 2021-02-24T19:54:21 Z Sorting Parrots (IOI11_parrots) C++17
100 / 100
 278 ms 211596 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

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

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 = 80;

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

# Verdict Execution time Memory Grader output
1 Correct 241 ms 210788 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 211256 KB Output is correct
2 Correct 247 ms 211120 KB Output is correct
3 Correct 248 ms 211188 KB Output is correct
4 Correct 262 ms 211060 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 211236 KB Output is correct
2 Correct 249 ms 211056 KB Output is correct
3 Correct 251 ms 211060 KB Output is correct
4 Correct 253 ms 211380 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 211184 KB Output is correct
2 Correct 264 ms 211060 KB Output is correct
3 Correct 251 ms 211220 KB Output is correct
4 Correct 251 ms 211212 KB Output is correct
5 Correct 258 ms 211448 KB Output is correct
6 Correct 255 ms 211228 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 211312 KB Output is correct - P = 5.000000
2 Correct 252 ms 211256 KB Output is correct - P = 5.000000
3 Correct 278 ms 211596 KB Output is correct - P = 5.000000
4 Correct 270 ms 211224 KB Output is correct - P = 5.000000
5 Correct 263 ms 211232 KB Output is correct - P = 5.000000
6 Correct 276 ms 211488 KB Output is correct - P = 5.000000
7 Correct 267 ms 211432 KB Output is correct - P = 5.000000