제출 #501303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501303		600Mihnea	Languages (IOI10_languages)	C++17	48 / 100	4125 ms	3112 KiB

lang

#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]]++;
  }

}

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