#include "lang.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) [&] { auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; return _x; }()
using pint = pair<int, int>;
double magic(double x) {
return pow(abs(x), 1.2);
}
template <typename T, int MAX>
struct Data : map<T, int> {
int tot = 0;
set<pair<int, T>> inv;
double operator&(const Data<T, MAX> &o) const {
double ret = 0;
for (auto [k, v]: *this) {
ret += magic((double) v / tot - (o.count(k) ? (double) o.at(k) / o.tot : 0));
}
for (auto [k, v]: o) {
if (not this->count(k)) ret += magic((double) v / o.tot);
}
return ret;
}
void operator+=(const Data<T, MAX> &o) {
for (auto &[k, v]: o) {
inv.erase({(*this)[k], k});
inv.emplace((*this)[k] += v, k);
}
tot += o.tot;
while (inv.size() > MAX) {
tot -= inv.begin()->first;
this->erase(inv.begin()->second);
inv.erase(inv.begin());
}
}};
struct Profile {
Data<int, 30> sing;
Data<pint, 50> doub;
Data<array<int, 3>, 50> trip;
Profile() {}
Profile(int *arr) {
for (int i = 0; i < 100; ++i) {
sing[arr[i]]++;
if (i) doub[{arr[i - 1], arr[i]}]++;
if (i >=2) trip[{arr[i - 2], arr[i - 1], arr[i]}];
}
for (auto [k, v]: doub) doub.inv.emplace(v, k);
sing.tot = 100;
doub.tot = 99;
trip.tot = 98;
}
double operator&(const Profile &o) const {
return (sing & o.sing) + (doub & o.doub) + (trip & o.trip);
}
void operator+=(const Profile &o) {
sing += o.sing;
doub += o.doub;
trip += o.trip;
}
} profile[56];
void excerpt(int *E) {
Profile p(E);
pair<double, int> mn{1e18, 0};
for (int i = 0; i < 56; ++i) {
mn = min(mn, {p & profile[i], i});
}
int ans = language(mn.second);
profile[ans] += p;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8105 ms |
6436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
7950 ms |
6560 KB |
Output is partially correct - 76.58% |
