#include <bits/stdc++.h>
#include "grader.h"
#include "lang.h"
using namespace std;
//int language(int ceva) {}
typedef long long ll;
typedef long double ld;
vector<int> so(vector<int> v) {
sort(v.begin(), v.end());
return v;
}
int getLoss(vector<pair<int, int>> a, vector<pair<int, int>> rl) {
int N = (int) a.size();
assert((int) a.size() == N);
assert((int) rl.size() == N);
sort(a.rbegin(), a.rend());
sort(rl.rbegin(), rl.rend());
vector<int> oa, ob;
map<int, int> tr;
for (int i = 0; i < N; i++) {
oa.push_back(a[i].second);
ob.push_back(rl[i].second);
tr[a[i].second] = i;
}
assert(so(oa) == so(ob));
for (int i = 0; i < N; i++) {
assert(tr.count(ob[i]));
ob[i] = tr[ob[i]];
}
int loss = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
loss += (2 * N - (i + j)) * (ob[i] > ob[j]);
}
}
return loss;
}
const int N = 100;
const int L = 56;
const int M = 65535 + 7;
int current[L][M];
set<pair<int, int>> g[L];
bool act[M];
void excerpt(int *a) {
map<int, int> theMap;
for (int i = 0; i < N; i++) {
theMap[a[i]]++;
act[a[i]] = 1;
}
vector<pair<int, int>> now;
for (auto &it : theMap) {
now.push_back({it.second, it.first});
}
sort(now.begin(), now.end());
int T = 20;
if ((int) now.size() > T) now.resize(T);
int mn_loss = (int) 1e9, prediction = 0;
for (int l = 0; l < L; l++) {
if (g[l].empty()) {
for (int i = 0; i < M; i++) {
assert(current[l][i] == 0);
g[l].insert({0, i});
}
}
vector<pair<int, int>> rl;
for (auto &it : now) {
rl.push_back({current[l][it.second], it.second});
}
vector<pair<int, int>> nw_now = now;
for (auto &it : g[l]) {
if ((int) rl.size() == (int) now.size() + 10) break;
int x = it.second;
if (act[x]) {
continue;
}
rl.push_back({current[l][x], x});
nw_now.push_back({theMap[x], x});
}
int loss_l = getLoss(nw_now, rl);
if (loss_l < mn_loss) {
prediction = l;
mn_loss = loss_l;
}
}
int solution = language(prediction);
for (int i = 0; i < N; i++) {
g[solution].erase({-current[solution][a[i]], a[i]});
current[solution][a[i]]++;
g[solution].insert({-current[solution][a[i]], a[i]});
act[a[i]] = 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5698 ms |
175260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
5561 ms |
175248 KB |
Output is partially correct - 53.48% |
