Submission #1011513

#TimeUsernameProblemLanguageResultExecution timeMemory
1011513Double_SlashLanguages (IOI10_languages)C++17
93 / 100
8476 ms8532 KiB
#pragma GCC optimize("O3,unroll-all-loops,inline") #pragma GCC target("avx2") #include "lang.h" #include "grader.h" #include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; using ll = long long; using pint = pair<int, int>; int ghost = 0; double magic(double x) { return exp(abs(x) * 1.5) - 1; } template <typename T, class Hash, int MAX> struct Data { int tot = 0; unordered_map<T, int, Hash> m; set<pair<int, T>> inv; double operator&(const Data<T, Hash, MAX> &o) const { double ret = 0; for (auto [k, v]: m) { ret += magic((double) v / tot - (o.m.find(k) != m.end() ? (double) o.m.find(k)->second / o.tot : 0)); } for (auto [k, v]: o.m) { if (m.find(k) == m.end()) ret += magic((double) v / o.tot); } return ret; } void operator+=(const Data<T, Hash, MAX> &o) { for (auto &[k, v]: o.m) { inv.erase({m[k], k}); inv.emplace(m[k] += v, k); } tot += o.tot; while (inv.size() > MAX) { tot -= inv.begin()->first; m.erase(inv.begin()->second); inv.erase(inv.begin()); } }}; struct hash1 { int operator()(const int x) const { return ((long long)x) * 327821 % 1000000007; } }; struct hash2 { ll operator() (const pint &x) const { return ((x.first) * 37) ^ ((x.second) * 73); } }; struct hash3 { ll operator()(const array<int, 3> &x) const { return (x[0] * 37) ^ (x[1] * 73) ^ (x[2] * 409); } }; struct Profile { Data<int, hash1, 50> sing; Data<pint, hash2, 300> doub; Data<array<int, 3>, hash3, 50> trip; Profile() {} Profile(int *arr) { for (int i = 0; i < 100; ++i) { sing.m[arr[i]]++; if (i) doub.m[{arr[i - 1], arr[i]}]++; if (i >=2) trip.m[{arr[i - 2], arr[i - 1], arr[i]}]; } for (auto [k, v]: sing.m) sing.inv.emplace(v, k); for (auto [k, v]: doub.m) doub.inv.emplace(v, k); for (auto [k, v]: trip.m) trip.inv.emplace(v, k); sing.tot = 100; doub.tot = 99; trip.tot = 98; } double operator&(const Profile &o) const { return (sing & o.sing) + (ghost > 0 ? (doub & o.doub) + (trip & o.trip) : 0); } 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; ghost++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...