Submission #699631

#	Time	Username	Problem	Language	Result	Execution time	Memory
699631		qwerasdfzxcl	Languages (IOI10_languages)	C++17	96 / 100	1645 ms	11176 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;
unordered_set<int> st[101];
bool st2[101][100100];
bool st3[101][100100];
bool st4[101][100100];
unordered_set<ull> st5[101];
int fail[101][101], iter, cnt[101];

unsigned short myHash(ull x){
    return (unsigned short)(x ^ x>>10 ^ x>>20 ^ x>>30 ^ x>>40 ^ x>>50 ^ x>>60);
}

void push(int *E, int typ){

    //for (int i=0;i<100;i++) st[typ].insert(E[i]);
    for (int i=0;i<99;i++) st2[typ][myHash(E[i]<<16 | E[i+1])] = 1;
    for (int i=0;i<98;i++) st3[typ][myHash((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;
    //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].find(E[i])==st[typ].end()) ret++;
    //}
    for (int i=0;i<99;i++){
        auto x = myHash(E[i]<<16 | E[i+1]);
        if (!st2[typ][x]) ret++;
    }

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

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

    //for (int i=0;i<96;i++){
    //    ull x = (ull)E[i]<<50 ^ (ull)E[i+1]<<40 ^ (ull)E[i+2]<<30 ^ (ull)E[i+3]<<20 ^ (ull)E[i+4]<<10;
    //    if (st5[typ].find(x)==st5[typ].end()) 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);
    //if (iter>=5000 && idx!=L) printf("%d / %d\n", calc(E, idx), calc(E, L));
    push(E, L);
    cnt[L]++;
    fail[idx][L]++;

    /*if (iter==10000){
        vector<pair<int, pair<int, int>>> V;
        for (int i=0;i<56;i++){
            for (int j=0;j<56;j++) if (i!=j){
                V.emplace_back(fail[i][j], make_pair(i, j));
            }
        }

        sort(V.begin(), V.end(), greater<pair<int, pair<int, int>>>());
        for (int z=0;z<10;z++){
            printf("fail %d(%s) (ans = %d(%s)): %d\n", V[z].second.first, I[V[z].second.first].c_str(), V[z].second.second, I[V[z].second.second].c_str(), V[z].first);
        }
    }*/
}

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