Submission #511328

#	Time	Username	Problem	Language	Result	Execution time	Memory
511328		600Mihnea	Languages (IOI10_languages)	C++17	0 / 100	10091 ms	176272 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 += (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});
  }
  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() == 100) break;
      int x = it.second;
      if (act[x]) {
        continue;
      }
      rl.push_back({current[l][x], x});
      nw_now.push_back({0, 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;
  }

}

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