제출 #146339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146339		popovicirobert	Languages (IOI10_languages)	C++14	0 / 100	10 ms	1792 KiB

lang

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;

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

#define SZ 100

const int B = (int) 1e9 + 7;

unordered_map <ull, int> mp[60];
bool ok[60][66000];
bool vis[60];

inline ll myrand() {
    return (1LL * rand() << 15) + rand();
}

void excerpt(int *E) {
    int i, j;

    vector < vector <int> > arr(56, vector <int>(5));

    int id = -1;
    for(int len = 4; len >= 1 && id == -1; len--) {
        ull cur = 0, pw = 1;
        for(i = 1; i < len; i++) {
            pw *= B;
        }
        for(i = 0; i + len <= 100 && id == -1; i++) {
            cur = cur * B + E[i];
            if(i >= len - 1) {
                for(int j = 0; j < 56; j++) {
                    arr[j][len] += mp[j][cur];
                }
                cur -= pw * E[i - len + 1];
            }
        }
    }
    vector <int> ord(56);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](const int &x, const int &y) {
                for(int i = 4; i >= 0; i--) {
                    if(arr[x][i] < arr[y][i]) {
                        return 1;
                    }
                    if(arr[x][i] > arr[y][i]) {
                        return 0;
                    }
                }
                return 1;
         });

    if(id == -1) {
        unordered_map <int, int> aux;
        for(i = 0; i < 100; i++) {
            aux[E[i]] = 1;
        }
        int mx = 0;
        for(i = 0; i < 56; i++) {
            int cur = 0;
            for(auto it : aux) {
                cur += ok[i][it.first];
            }
            if(cur > mx) {
                mx = cur, id = i;
            }
        }

        if(id == -1) {
            vector <int> ids;
            for(i = 0; i < 56; i++) {
                if(vis[i] == 0) ids.push_back(i);
            }
            int sz = ids.size();
            id = ids[myrand() % sz];
        }
    }

    id = language(id);
    for(i = 0; i < 100; i++) {
        ull cur = 0;
        for(j = i; j < i + 4 && j < 100; j++) {
            cur = cur * B + E[j];
            mp[id][cur]++;
        }
        ok[id][E[i]] = 1;
    }
    vis[id] = 1;
}

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