Submission #699898

#	Time	Username	Problem	Language	Result	Execution time	Memory
699898		qwerasdfzxcl	Languages (IOI10_languages)	C++17	100 / 100	5632 ms	38560 KiB

lang

#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
constexpr ll DIG = 1e5, B = 57;
bool st[101][100100];
bool st2[101][100100];
bool st22[101][100100];

bool st3[101][100100];
bool st32[101][100100];
bool st4[101][100100];
bool st42[101][100100];

bool st5[101][100100];
bool st52[101][100100];
bool st6[101][100100];
bool st62[101][100100];
int fail[101][101], iter, cnt[101];

ll S[100100], S2[100100];
int T[100100], T2[100100];

unsigned short myHash(ull x){
    return (unsigned short)(x ^ x>>11 ^ x>>22 ^ x>>33 ^ x>>44 ^ x>>55);
}

unsigned short myHash2(ull x){
    return (unsigned short)(x ^ x>>13 ^ x>>26 ^ x>>39 ^ x>>52);
}

void push(int *E, int typ){
    for (int i=0;i<100;i++){
        S[E[i]] |= 1LL<<(typ);
        T[E[i]]++;
    }

    for (int i=0;i<100;i++) st[typ][E[i]] = 1;
    for (int i=0;i<99;i++){
        st2[typ][myHash(E[i]<<16 | E[i+1])] = 1;
        st22[typ][myHash2(E[i]<<16 | E[i+1])] = 1;

        S2[myHash(E[i]<<16 | E[i+1])] |= 1LL<<(typ);
        T2[myHash(E[i]<<16 | E[i+1])]++;
    }
    for (int i=0;i<98;i++){
        st3[typ][myHash((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2])] = 1;
        st32[typ][myHash2((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2])] = 1;
    }
    for (int i=0;i<97;i++){
        st4[typ][myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]))] = 1;
        st42[typ][myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]))] = 1;
    }

    for (int i=0;i<96;i++){
        auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]);
        auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]);
        st5[typ][x] = 1;
        st52[typ][y] = 1;
    }

    for (int i=0;i<95;i++){
        auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]<<16 | E[i+5]);
        auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]<<16 | E[i+5]);
        st6[typ][x] = 1;
        st62[typ][y] = 1;
    }
    //for (int i=0;i<96;i++) st5[typ].insert((ull)E[i]<<50 ^ (ull)E[i+1]<<40 ^ (ull)E[i+2]<<30 ^ (ull)E[i+3]<<20 ^ (ull)E[i+4]<<10);
}

int calc(int *E, int typ){
    int ret = 0;
    for (int i=0;i<100;i++){
        if (!st[typ][E[i]]) ret++;
        if (__builtin_popcountll(S[E[i]])==1 && S[E[i]] == (1LL<<typ) && T[E[i]] >= 3) ret -= 10;
    }
    for (int i=0;i<99;i++){
        auto x = (E[i]<<16 | E[i+1]);
        if (!st2[typ][myHash(x)] || !st22[typ][myHash2(x)]) ret++;
        if (__builtin_popcountll(S2[myHash(x)])==1 && S2[myHash(x)] == (1LL<<typ) && T2[myHash(x)] >= 3) ret -= 10;
    }

    for (int i=0;i<98;i++){
        auto x = ((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2]);
        if (!st3[typ][myHash(x)] || !st32[typ][myHash2(x)]) ret++;
    }

    for (int i=0;i<97;i++){
        auto x = ((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]);
        if (!st4[typ][myHash(x)] || !st42[typ][myHash2(x)]) ret++;
    }

    for (int i=0;i<96;i++){
        auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]);
        auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]);
        if (!st5[typ][x] || !st52[typ][y]) ret++;
    }

    for (int i=0;i<95;i++){
        auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]<<16 | E[i+5]);
        auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]<<16 | E[i+5]);
        if (!st6[typ][x] || !st62[typ][y]) ret++;
    }
    return ret;
}

int X[101];
void excerpt(int *E){
    ++iter;

    int idx = -1;
    for (int i=0;i<56;i++){
        X[i] = calc(E, i);
    }

    idx = min_element(X, X+56) - X;

    int L = language(idx);
    push(E, L);
    cnt[L]++;
    fail[idx][L]++;

}

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