Submission #146390

#	Time	Username	Problem	Language	Result	Execution time	Memory
146390		popovicirobert	Languages (IOI10_languages)	C++14	98 / 100	4386 ms	22304 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) 1e5;

unordered_set <ull> ok[60];
bool vis[60];

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

void excerpt(int *E) {
    int i, j;
    unordered_set <ull> mp;
    for(i = 0; i + 4 <= 100; i++) {
        ull cur = 0;
        for(j = i; j < i + 4; j++) {
            cur = (cur << 16) + E[j];
        }
        mp.insert(cur);
    }

    vector <int> arr(56);
    int id = -1;
    for(auto it : mp) {
        for(i = 0; i < 56; i++) {
            if(ok[i].find(it) != ok[i].end()) {
                arr[i]++;
            }
        }
    }
    id = max_element(arr.begin(), arr.end()) - arr.begin();
    if(arr[id] == 0) {
        vector <int> ids;
        int sz = 0;
        for(i = 0; i < 56; i++) {
            if(vis[i] == 0) {
                ids.push_back(i);
                sz++;
            }
        }
        if(sz > 0) {
            id = ids[myrand() % sz];
        }
    }

    id = language(id);
    for(i = 0; i + 4 <= 100; i++) {
        ull cur = 0;
        for(j = i; j < i + 4; j++) {
            cur = (cur << 16) + E[j];
        }
        ok[id].insert(cur);
    }
    vis[id] = 1;
}

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