Submission #509815

#	Time	Username	Problem	Language	Result	Execution time	Memory
509815		600Mihnea	Archery (IOI09_archery)	C++17	0 / 100	21 ms	22840 KiB

archery

#include <bits/stdc++.h>

using namespace std;

const int N = 2 * 200000 + 7;
const int INF = (int) 1e9 + 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;
int thesol[N];


int 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++) {
    for (int it = 0; it < 2; it++) {
      ord[2 * i + it] = guys[i][it];
    }
  }
  return (loser[0] == my_rank);
}

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

int get_brute(int pos) {
  pos = 2 * pos;
  int sol = -1, ans = 0;
  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++) {
    ans += 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 - ans * n;
}

int rep(int x) {
  x %= n;
  if (x < 0) x += n;
  return x;
}

enum TYPE {BIG, SMALL, EQUAL};

int cnt_big[N];
int cnt_equal[N];

TYPE type[N];

int get_smart(int x) {
  if (my_rank == 0) {
    return 0;
  }
  if (my_rank <= n) {
    int pos = 2 * x;
    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];
    }
    set<pair<int, int>> guys;
    for (int i = 0; i < 2 * n; i++) {
      guys.insert({i / 2, ord[i]});
    }
    int ant = max(ord[0], ord[1]);
    set<int> inside;
    vector<int> mxs;
    for (int iter = 1; iter <= r; iter++) {
      while (!guys.empty() && guys.begin()->first < iter) {
        inside.insert(guys.begin()->second);
        guys.erase(guys.begin());
      }
      assert(!inside.empty());

      auto smallestIt = inside.begin();
      int smallest = *smallestIt;
      inside.erase(smallestIt);
      if (iter == 1) {
        inside.clear();
      }
      int nw = iter - 1 + n;
      int mx = max(smallest, ant);
      int mn = min(smallest, ant);
      mxs.push_back(mx);
      ant = mn;
      guys.insert({nw, mx});
    }
    int last_seen = -1, transfering = 0;
    for (int i = 0; i < r; i++) {
      if (mxs[i] == my_rank) {
        last_seen = i;
        transfering++;
      }
    }
    int thepos = n - (r - 1 - last_seen) - 1;
    return thepos - n * transfering;
  }
  assert(my_rank >= n + 1);
  int pos = 2 * x;
  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];
  }
  for (int i = 0; i < 2 * n; i++) {
    if (ord[i] == my_rank) {
      type[i] = EQUAL;
    }
    if (ord[i] > my_rank) {
      type[i] = BIG;
    }
    if (ord[i] < my_rank) {
      type[i] = SMALL;
    }
  }
  for (int i = 0; i < n; i++) {
    cnt_big[i] = (type[2 * i] == BIG) + (type[2 * i + 1] == BIG);
    cnt_equal[i] = (type[2 * i] == EQUAL) + (type[2 * i + 1] == EQUAL);
  }
  int big_in_hand = 0, equal_in_hand = 0, transfering = 0;
  function<void()> handle0 = [&] () {
    assert(0 <= equal_in_hand && equal_in_hand <= 1);
    assert(0 <= big_in_hand);
    assert(0 <= cnt_equal[0] && cnt_equal[0] <= 1);
    assert(0 <= cnt_big[0] && cnt_big[0] <= 2);

    /// if EQUAL vs BIG => EQUAL remains, BIG goes

    int the_sum = cnt_big[0] + cnt_equal[0];
    big_in_hand += cnt_big[0];
    equal_in_hand += cnt_equal[0];
    cnt_big[0] = cnt_equal[0] = 0;

    if (the_sum != 2) {
      /// there is a small one and it pushes them away
      transfering += (equal_in_hand);
      return;
    }

    if (equal_in_hand) {
      assert(equal_in_hand == 1);
      cnt_equal[0] = 1;
      equal_in_hand = 0;
    } else {
      if (big_in_hand) {
        cnt_big[0] = 1;
        big_in_hand--;
      }
    }
    transfering += (equal_in_hand);
  };
  function<void(int)> handlenot0 = [&] (int i) {
    assert(0 <= equal_in_hand && equal_in_hand <= 1);
    assert(0 <= big_in_hand);
    assert(0 <= cnt_equal[0] && cnt_equal[0] <= 1);
    assert(0 <= cnt_big[0] && cnt_big[0] <= 2);

    /// if EQUAL vs BIG => BIG remains, EQUAL goes
    big_in_hand += cnt_big[i];
    equal_in_hand += cnt_equal[i];

    cnt_big[i] = cnt_equal[i] = 0;

    if (big_in_hand) {
      cnt_big[i] = 1;
      big_in_hand--;
    } else {
      if (equal_in_hand) {
        assert(equal_in_hand == 1);
        cnt_equal[i] = 1;
        equal_in_hand = 0;
      }
    }
  };
  function<void()> printsituation = [&] () {
    for (int i = 0; i < n; i++) {
      cout << "(" << cnt_equal[i] << ", " << cnt_big[i] << ") ";
    }
    cout << " | " << equal_in_hand << " vs " << big_in_hand << "\n";
  };

 // printsituation();
  handle0();
 // printsituation();  exit(0);
  for (int i = n - 1; i >= 1; i--) handlenot0(i);

  handle0();
  for (int i = n - 1; i >= 1; i--) handlenot0(i);

  int thepos = -1;
  for (int i = 0; i < n; i++) {
    if (cnt_equal[i]) {
      thepos = i;
    }
  }
  assert(thepos != -1);

  return thepos - n * transfering;

  int val = get_brute(x);

  cout << val << " vs " << thepos - n * transfering << "\n";


  return val;
}

int get(int x) {
  if (thesol[x] != INF) {
    return thesol[x];
  }
  thesol[x] = get_smart(x);
  return thesol[x];
}



int mn = (int) 1e9;
int best = -1;

void upd(int i) {
  int x = get(i);
  int y = rep(x);
  if (y < mn) {
    mn = y;
    best = i;
  } else {
    if (y == mn) {
      best = max(best, i);
    }
  }
}

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

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

  for (int i = 0; i < N; i++) {
    thesol[i] = INF;
  }

  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]--;
  }
  upd(0);
  upd(n - 1);
  {
    int low = 0, high = n - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      upd(mid);
      if (get(mid) == get(0)) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  int L = get(0), R = get(n - 1);
  for (int j = L; j <= R; j++) {
    if (j % n) {
      continue;
    }
    int low = 0, high = n - 1, the_value = INF;
    while (low <= high) {
      int mid = (low + high) / 2;
      upd(mid);
      if (get(mid) >= j) {
        high = mid - 1;
        the_value = mid;
      } else {
        low = mid + 1;
      }
    }
    low = the_value;
    high = n - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      upd(mid);
      if (get(mid) == get(the_value)) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  cout << best + 1 << "\n";
  return 0;
}

Compilation message (stderr)

archery.cpp: In function 'int main()':
archery.cpp:282:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  282 |   freopen ("input", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 94