oj.uz

Submission #2995

# Submission time Handle Problem Language Result Execution time Memory
2995 2013-08-20T09:01:30 Z tncks0121 Languages (IOI10_languages) C++
101 / 100
 5717 ms 55196 KB 
#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 < 100; j++) cnt += calc(freq1[i][E[j]]) * 3;
        for(j = 0; j < 99; j++) cnt += calc(freq2[i][hash2(E[j], E[j+1])]) * 111;
        for(j = 0; j < 98; j++) cnt += calc(freq3[i][hash3(E[j], E[j+1], E[j+2])]) * 50;
        for(j = 0; j < 97; j++) cnt += calc(freq4[i][hash4(E[j], E[j+1], E[j+2], E[j+3])]) * 91;
        cnt /= log(1+freq[i]);
        if(cnt > retc) ret = i, retc = cnt;
    }
    
    int lang = language(ret);
    ++freq[lang];
    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])]++;
    for(i = 0; i < 97; i++) freq4[lang][hash4(E[i], E[i+1], E[i+2], E[i+3])]++;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5717 ms 54748 KB Output is correct

Subtask #2
71.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5478 ms 55196 KB Output is correct - 92.33%