Submission #503516

#	Time	Username	Problem	Language	Result	Execution time	Memory
503516		600Mihnea	Archery (IOI09_archery)	C++17	20 / 100	2103 ms	23236 KiB

archery

#include <bits/stdc++.h>

using namespace std;

const int N = 2 * 200000 + 7;
int n;
int r;
int my_rank;
int init_ord[N];
int ord[N];
int winner[N];
int loser[N];
vector<int> guys[N];
bool wannap;

void simulate_step_for_get_brute() {
  for (int i = 0; i < n; i++) {
    if (ord[2 * i] < ord[2 * i + 1]) {
      winner[i] = ord[2 * i];
      loser[i] = ord[2 * i + 1];
    } else {
      winner[i] = ord[2 * i + 1];
      loser[i] = ord[2 * i];
    }
    guys[i].clear();
  }
  guys[0].push_back(winner[0]);
  for (int i = 1; i < n; i++) {
    guys[i - 1].push_back(winner[i]);
    guys[i].push_back(loser[i]);
  }
  guys[n - 1].push_back(loser[0]);
  for (int i = 0; i < n; i++) {
    assert((int) guys[i].size() == 2);
    for (int it = 0; it < 2; it++) {
      ord[2 * i + it] = guys[i][it];
    }
  }
}

void print() {
  cout << " ----> ";
  for (int i = 0; i < 2 * n; i++) {
    cout << ord[i] + 1 << " ";
  }
  cout << "\n";
}

int get_brute(int pos) {
  int sol = -1;
  assert(0 <= pos && pos < 2 * n);
  ord[pos] = my_rank;
  for (int i = 0; i < pos; i++) {
    ord[i] = init_ord[i];
  }
  for (int i = pos + 1; i < 2 * n; i++) {
    ord[i] = init_ord[i - 1];
  }
  if (wannap) print();
  for (int j = 1; j <= r; j++) {
    simulate_step_for_get_brute();
    if (wannap) print();
  }
  for (int i = 0; i < 2 * n; i++) {
    if (ord[i] == my_rank) {
      sol = i;
    }
  }
  if (wannap) cout << "= " << sol << "\n";
  assert(sol != -1);
  return sol / 2;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  wannap = 0;

  cin >> n >> r;
  r = 2 * n + r % n;
  cin >> my_rank;
  my_rank--;
  for (int i = 0; i < 2 * n - 1; i++) {
    cin >> init_ord[i];
    init_ord[i]--;
  }
 // get_brute(0);
  //exit(0);
  int mn = (int) 1e9, best = -1;
  for (int i = n - 1; i >= 0; i--) {
    int x = get_brute(2 * i);
    if (x < mn) {
      mn = x;
      best = i;
    }
  }
  cout << best + 1 << "\n";
  return 0;
}

• Subtask 1: 4 / 6
• Subtask 2: 16 / 94