Submission #82783

#	Time	Username	Problem	Language	Result	Execution time	Memory
82783		naoai	Languages (IOI10_languages)	C++14	99 / 100	7570 ms	157004 KiB

lang

#include <bits/stdc++.h>

using namespace std;

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

typedef unsigned long long u64;
static const int mod = 2e7 + 3;
static const int nmax = 100;
static const int lgmax = 7;
static const int nrlang = 56;
static const int base = 218279;

bool viz[nrlang];
int c[nmax + 1];

int p32[lgmax + 1];
u64 hp[nmax + 1][nmax + 1];

class Hash{
public:
    Hash() {
        for (int i = 0; i < mod; ++ i) {
            h[i] = 0;
        }
    }

    u64 h[mod];

    bool baga (u64 k) {
        int key = k % mod;
        while (h[key] != 0 && h[ key ] != k) {
            key = (1LL * key * hbase + hct) % mod;
        }
        if (h[ key ] == k) return 0;
        h[ key ] = k;
        return 1;
    }

    int cauta (u64 k) {
        int key = k % mod;
        while (h[key] != 0 && h[ key ] != k) {
            key = (1LL * key * hbase + hct) % mod;
        }
        if (h[ key ] == k) return 1;
        return 0;
    }
private:
    static const int hbase = 7919;
    static const long long hct = 2017;
} h;

void baga (int l, u64 x) {
    h.baga(x * 61 + l);
}

int cauta (int l, u64 x) {
    return h.cauta(x * 61 + l);
}

void excerpt(int *E) {
    int bstcost = -1, bstlang = 0;

    for (int i = 1; i <= lgmax; ++ i)
        p32[i] = i * i;

    for (int i = 1; i <= nmax; ++ i) {
        for (int j = i; j <= i + lgmax && j <= nmax; ++ j) {
            hp[i][j] = hp[i][j - 1] * base + E[j - 1];
        }
    }

    for (int l = 0; l < nrlang; ++ l) {
        if (viz[l] == 0)
            continue;
        c[0] = 0;

        for (int i = 1; i <= nmax; ++ i) {
            c[i] = 0;

            for (int j = max(0, i - lgmax); j < i; ++ j) {
                c[i] = max(c[i], c[j] + cauta(l, hp[j + 1][i]) * p32[i - j]);
            }
        }

        if (c[nmax] > bstcost) {
            bstcost = c[nmax];
            bstlang = l;
        }
    }

	int ans = language(bstlang);
	viz[ans] = 1;

	for (int i = 1; i <= nmax; ++ i) {
        for (int j = max(0, i - lgmax); j < i; ++ j) {
            baga(ans, hp[j + 1][i]);
        }
	}
}

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