답안 #511335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511335	2022-01-15T14:32:19 Z	600Mihnea	Languages (IOI10_languages)	C++17	0 / 100	4284 ms	175464 KB

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});
  }
  sort(now.begin(), now.end());
  int T = 10;
  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;
  }

}

Subtask #1

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4284 ms	175264 KB	Output isn't correct

Subtask #2

0.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4189 ms	175464 KB	Output isn't correct - 29.68%