Submission #2984

#	Time	Username	Problem	Language	Result	Execution time	Memory
2984		tncks0121	Languages (IOI10_languages)	C++98	97 / 100	3151 ms	32240 KiB

lang

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

#include "grader.h"
#include "lang.h"

#define SZ 100

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

typedef long long ll;

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

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

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 += !!(freq1[i][E[j]]) * 0.5;
        for(j = 0; j < 100; j++) cnt += (freq1[i][E[j]]) / (freq1[i][E[j]] + 0.1);
        for(j = 0; j < 99; j++) cnt += calc(freq2[i][hash2(E[j], E[j+1])]);
        for(j = 0; j < 98; j++) cnt += calc(freq3[i][hash3(E[j], E[j+1], E[j+2])]);
        if(cnt > retc) ret = i, retc = cnt;
    }
    
    int lang = language(ret);
    for(i = 0; i < 100; i++) freq1[lang][E[i]]++;
    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])]++;
}

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