#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 += (N - ob[i]) * (ob[i] > ob[j]);
}
}
return loss;
}
const int N = 100;
const int L = 56;
const int M = 65535 + 7;
int current[L][M];
void excerpt(int *a) {
map<int, int> theMap;
for (int i = 0; i < N; i++) {
theMap[a[i]]++;
}
vector<pair<int, int>> now;
for (auto &it : theMap) {
now.push_back({it.second, it.first});
}
int mn_loss = (int) 1e9, prediction = 0;
for (int l = 0; l < L; l++) {
vector<pair<int, int>> rl;
for (auto &it : now) {
rl.push_back({current[l][it.second], it.second});
}
int loss_l = getLoss(now, rl);
if (loss_l < mn_loss) {
prediction = l;
mn_loss = loss_l;
}
}
int solution = language(prediction);
for (int i = 0; i < N; i++) {
current[solution][a[i]]++;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4125 ms |
3112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
4122 ms |
2936 KB |
Output is partially correct - 46.15% |
