Submission #199362

#	Time	Username	Problem	Language	Result	Execution time	Memory
199362		alexandra_udristoiu	Parrots (IOI11_parrots)	C++14	100 / 100	634 ms	66800 KiB

encoder

#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);
    }
}

decoder

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19