Submission #2996

#	Time	Username	Problem	Language	Result	Execution time	Memory
2996		tncks0121	Languages (IOI10_languages)	C++98	101 / 100	5283 ms	52256 KiB

lang

#include <stdlib.h>
#include <stdio.h>

#include "grader.h"
#include "lang.h"
#include <math.h>
#define SZ 100

const int L = 56;
const int C = 65536;
const int H = 79378;

typedef long long ll;

int freq1[L][C];
int freq2[L][H];
int freq3[L][H];
int freq4[L][H];
int freq[L];

int hash2 (int a, int b) {
    return (((ll)a<<16) | b) % H;
}

int hash3 (int a, int b, int c) {
    return (((ll)hash2(a, b)<<16) | c) % H;
}

int hash4 (int a, int b, int c, int d) {
    return (((ll)hash3(a, b, c)<<16) | d) % H;
}

double calc (double v) {
    return v / (v + 1.0);
}

void excerpt(int *E) {
    int i, j;
    int ret = 0; double retc = 0;
    
    for(i = 0; i < L; i++) {
        double cnt = 0;
        for(j = 0; j < 99; j++) cnt += calc(freq2[i][hash2(E[j], E[j+1])]) * 138;
        for(j = 0; j < 98; j++) cnt += calc(freq3[i][hash3(E[j], E[j+1], E[j+2])]) * 60;
        for(j = 0; j < 97; j++) cnt += calc(freq4[i][hash4(E[j], E[j+1], E[j+2], E[j+3])]) * 97;
        cnt /= log(1+freq[i]);
        if(cnt > retc) ret = i, retc = cnt;
    }
    
    int lang = language(ret);
    ++freq[lang];
    for(i = 0; i < 99; i++) freq2[lang][hash2(E[i], E[i+1])]++;
    for(i = 0; i < 98; i++) freq3[lang][hash3(E[i], E[i+1], E[i+2])]++;
    for(i = 0; i < 97; i++) freq4[lang][hash4(E[i], E[i+1], E[i+2], E[i+3])]++;
}

• Subtask 1: 30 / 30
• Subtask 2: 71 / 80