oj.uz

Submission #199362

# Submission time Handle Problem Language Result Execution time Memory
199362 2020-01-31T16:16:38 Z alexandra_udristoiu Parrots (IOI11_parrots) C++14
100 / 100
 634 ms 66800 KB 
#include<iostream>
#include<cstring>
#include "encoder.h"
#include "encoderlib.h"
#define base 5000000
using namespace std;
static int d[350][260][100], pt[70][100], num[100];
static void adun(int a[], int b[], int c[]){
    int i, t = 0;
    c[0] = max(a[0], b[0]);
    for(i = 1; i <= c[0]; i++){
        c[i] = t + a[i] + b[i];
        t = c[i] / base;
        c[i] %= base;
    }
    if(t != 0){
        c[ ++c[0] ] = t;
    }
}
static void mult(int a[], int x, int b[]){
    int i, t = 0;
    b[0] = a[0];
    for(i = 1; i <= a[0]; i++){
        b[i] = a[i] * x + t;
        t = b[i] / base;
        b[i] %= base;
    }
    while(t != 0){
        b[ ++b[0] ] = t % base;
        t /= base;
    }
}
static void scad(int a[], int b[]){
    int i, t = 0;
    for(i = 1; i <= a[0]; i++){
        if(a[i] < b[i] + t){
            a[i] = a[i] + base - b[i] - t;
            t = 1;
        }
        else{
            a[i] -= b[i] + t;
            t = 0;
        }
    }
    while(a[0] > 1 && a[ a[0] ] == 0){
        a[0]--;
    }
}
static int comp(int a[], int b[]){
    if(a[0] != b[0]){
        if(a[0] < b[0]){
            return 1;
        }
        return 0;
    }
    for(int i = a[0]; i >= 1; i--){
        if(a[i] != b[i]){
            if(a[i] < b[i]){
                return 1;
            }
            return 0;
        }
    }
    return 0;
}
static void calcpt(int n){
    pt[0][0] = 1; pt[0][1] = 1;
    for(int i = 1; i <= n; i++){
        mult(pt[i - 1], 256, pt[i]);
    }
}
static void calcdp(int n){
    int i, j;
    memset(num, 0, sizeof(num) );
    for(j = 0; j < 256; j++){
        d[n - 1][j][0] = d[n - 1][j][1] = 1;
    }
    for(i = n - 2; i >= 0; i--){
        for(j = 255; j >= 0; j--){
            adun(d[i + 1][j], d[i][j + 1], d[i][j]);
        }
    }
}
void encode(int n, int v[]){
    int i, j, x, k = 5 * n - 1;
    calcdp(k);
    calcpt(n);
    for(i = 0; i < n; i++){
        for(j = 0; j < v[i]; j++){
            adun(num, pt[n - i - 1], num);
        }
    }
    adun(num, pt[0], num);
    x = 0;
    for(i = 0; i < k; i++){
        while( comp(d[i][x], num) ){
            scad(num, d[i][x]);
            x++;
        }
        send(x);
    }
}

#include<iostream>
#include<algorithm>
#include<cstring>
#define base 5000000
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
static int d[350][260][100], pt[70][100], num[100];
static void adun(int a[], int b[], int c[]){
    int i, t = 0;
    c[0] = max(a[0], b[0]);
    for(i = 1; i <= c[0]; i++){
        c[i] = t + a[i] + b[i];
        t = c[i] / base;
        c[i] %= base;
    }
    if(t != 0){
        c[ ++c[0] ] = t;
    }
}
static void mult(int a[], int x, int b[]){
    int i, t = 0;
    b[0] = a[0];
    for(i = 1; i <= a[0]; i++){
        b[i] = a[i] * x + t;
        t = b[i] / base;
        b[i] %= base;
    }
    while(t != 0){
        b[ ++b[0] ] = t % base;
        t /= base;
    }
}
static void scad(int a[], int b[]){
    int i, t = 0;
    for(i = 1; i <= a[0]; i++){
        if(a[i] < b[i] + t){
            a[i] = a[i] + base - b[i] - t;
            t = 1;
        }
        else{
            a[i] -= b[i] + t;
            t = 0;
        }
    }
    while(a[0] > 1 && a[ a[0] ] == 0){
        a[0]--;
    }
}
static int comp(int a[], int b[]){
    if(a[0] != b[0]){
        if(a[0] < b[0]){
            return 1;
        }
        return 0;
    }
    for(int i = a[0]; i >= 1; i--){
        if(a[i] != b[i]){
            if(a[i] < b[i]){
                return 1;
            }
            return 0;
        }
    }
    return 0;
}
static void calcpt(int n){
    pt[0][0] = 1; pt[0][1] = 1;
    for(int i = 1; i <= n; i++){
        mult(pt[i - 1], 256, pt[i]);
    }
}
static void calcdp(int n){
    int i, j;
    for(j = 0; j < 256; j++){
        d[n - 1][j][0] = d[n - 1][j][1] = 1;
    }
    for(i = n - 2; i >= 0; i--){
        for(j = 255; j >= 0; j--){
            adun(d[i + 1][j], d[i][j + 1], d[i][j]);
        }
    }
}
void decode(int n, int k, int v[]){
    int i, x, j;
    memset(num, 0, sizeof(num) );
    calcpt(n);
    calcdp(k);
    sort(v, v + k);
    for(j = 0; j < v[i]; j++){
        adun(num, d[0][j], num);
    }
    for(i = 1; i < k; i++){
        for(j = v[i - 1]; j < v[i]; j++){
            adun(num, d[i][j], num);
        }
    }
    adun(num, pt[0], num);
    for(i = 0; i < n; i++){
        for(j = 0; j < 256; j++){
            if(comp(pt[n - i - 1], num) == 0){
                output(j);
                break;
            }
            else{
                scad(num, pt[n - i - 1]);
            }
        }
    }
}

Compilation message

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:85:12: warning: unused variable 'x' [-Wunused-variable]
     int i, x, j;
            ^
decoder.cpp:90:23: warning: 'i' is used uninitialized in this function [-Wuninitialized]
     for(j = 0; j < v[i]; j++){
                       ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8980 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9456 KB Output is correct
2 Correct 36 ms 12528 KB Output is correct
3 Correct 60 ms 16632 KB Output is correct
4 Correct 56 ms 17648 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9456 KB Output is correct
2 Correct 39 ms 12528 KB Output is correct
3 Correct 59 ms 16624 KB Output is correct
4 Correct 59 ms 17656 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9456 KB Output is correct
2 Correct 65 ms 17648 KB Output is correct
3 Correct 84 ms 21744 KB Output is correct
4 Correct 182 ms 31984 KB Output is correct
5 Correct 200 ms 33264 KB Output is correct
6 Correct 230 ms 34032 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17656 KB Output is correct - P = 4.937500
2 Correct 222 ms 34040 KB Output is correct - P = 4.968750
3 Correct 225 ms 35288 KB Output is correct - P = 4.969697
4 Correct 445 ms 52464 KB Output is correct - P = 4.980000
5 Correct 558 ms 62704 KB Output is correct - P = 4.983333
6 Correct 606 ms 65776 KB Output is correct - P = 4.984127
7 Correct 634 ms 66800 KB Output is correct - P = 4.984375