Submission #1153207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153207		m_bezrutchka	Jousting tournament (IOI12_tournament)	C++20	0 / 100	12 ms	512 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

int n, c, r;
vector<int> s, e, p;

vector< vector<int> > adj;
vector<int> pai;
vector<int> id;
vector<int> label;
int sz;

int add_node(vector<int> &children) {
  adj.push_back({});
  pai.push_back(-1);
  id.push_back(sz);
  for (int x: children) {
    id[sz] = min(id[sz], id[x]);
    pai[x] = sz;
    adj[sz].push_back(x);
  }
  int ret = sz;
  sz++;
  return ret;
}

void print_node(int idx) {
  cerr << idx << ": ";
  cerr << "pai = " << pai[idx] << " | filhos =";
  for (int x: adj[idx]) {
    cerr << " " << x;
  }
  cerr << "\n";
}

void build_tree() {
  vector<int> players;
  for (int i = 0; i < n; i++) {
    add_node(players);
  }
  vector<int> rep(c);
  for (int i = 0; i < c; i++) {
    vector<pair<int,int>> heads;
    for (int j = 0; j < sz; j++) {
      if (pai[j] == -1) {
        heads.push_back({id[j], j});
      }
    }
    sort(heads.begin(), heads.end());
    players.clear();
    for (int j = s[i]; j <= e[i]; j++) {
      players.push_back(heads[j].second);
    }
    rep[i] = add_node(players);
  }
  cerr << "Finished building tree:\n";
  cerr << "Leaves:\n";
  for (int i = 0; i < n; i++) {
    print_node(i);
  }
  cerr << "Non-leaves:\n";
  for (int i = n; i < sz; i++) {
    print_node(i);
  }
}

int cnt_cur;

void dfs(int v) {
  if (adj[v].empty()) {
    return;
  } else {
    label[v] = label[adj[v][0]];
    for (int x: adj[v]) {
      dfs(x);
      label[v] = max(label[v], label[x]);
    }
    if (label[v] == r) {
      cnt_cur++;
    }
  }
}

int get_wins(vector<int> &v, int pos) {
  label.resize(sz);
  for (int i = 0; i < n; i++) {
    label[i] = v[i];
  }
  cnt_cur = 0;
  dfs(sz - 1);
  return cnt_cur;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  n = N; c = C; r = R; s.clear(); e.clear(); p.clear();
  for (int i = 0; i < n; i++) {
    p.push_back(K[i]);
  }
  for (int i = 0; i < c; i++) {
    s.push_back(S[i]);
    e.push_back(E[i]);
  }
  build_tree();

  int best_resp = -1, best_pos = -1;
  for (int pos = 0; pos < n; pos++) {
    vector<int> vals;
    for (int i = 0; i < pos; i++) {
      vals.push_back(p[i]);
    }
    vals.push_back(r);
    for (int i = pos; i < n - 1; i++) {
      vals.push_back(p[i]);
    }
    int cur = get_wins(vals, pos);
    if (cur > best_resp) {
      best_resp = cur;
      best_pos = pos;
    }
  }

  return best_pos;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51