oj.uz

Submission #509796

# Submission time Handle Problem Language Result Execution time Memory
509796 2022-01-14T09:58:31 Z 600Mihnea Archery (IOI09_archery) C++17
39 / 100
 2000 ms 42136 KB 
#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];

vector<int> johnny;

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++) {
    assert((int) guys[i].size() == 2);
    for (int it = 0; it < 2; it++) {
      ord[2 * i + it] = guys[i][it];
    }
  }
  johnny.push_back(loser[0]);
  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;
}

void print(vector<int> v) {
  cout << " ----> ";
  for (auto &x : v) {
    cout << x << " ";
  }
  cout << "\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];
    }
    if (0) {
      for (int i = 0; i < 2 * n; i++) {
        cout << ord[i] << " ";
      }
      cout << " = init, my_rank = " << my_rank << "\n";
    }
    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++) {
      /// delete all elements
      /*if (iter == 2) {
        cout << " -----------> ";
        for (auto &x : inside) {
          cout << x << " ";
        }
        cout << "\n";
      }*/
      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; /// poate este iter + n????????????????????????????????
      int mx = max(smallest, ant);
      int mn = min(smallest, ant);
      mxs.push_back(mx);
      ant = mn;
      /*if (iter <= 2) {
        cout << mn << " remains, " << mx << " goes\n";
        if (iter == 2) {
          cout << "ant = " << ant << "\n";
          cout << smallest << "\n";
        }
      }*/
      guys.insert({nw, mx});
    }
  ///print(mxs);
   // exit(0);
    ///assert((int) mxs.size() == r);
    int last_seen = -1, transfering = 0;
    for (int i = 0; i < r; i++) {
      if (mxs[i] == my_rank) {
        last_seen = i;
        transfering++;
      }
    }
    assert(last_seen != -1);
    /// p -> n - 1
    /// p + 1 -> n - 2
    /// p + i -> n - i - 1
    /// p + (r - 1 - p) -> n - (r - 1 - p) - 1
    int thepos = n - (r - 1 - last_seen) - 1;
    int val = get_brute(x);
    assert(thepos - n * transfering == val);
    return val;
  }
  return get_brute(x);
}

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;
}

Subtask #1
5.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11260 KB Output is correct
2 Correct 6 ms 11276 KB Output is correct
3 Correct 12 ms 11280 KB Output is correct
4 Execution timed out 2084 ms 12388 KB Time limit exceeded
5 Correct 6 ms 11340 KB Output is correct
6 Correct 18 ms 11340 KB Output is correct

Subtask #2
34.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11212 KB Output is correct
2 Correct 32 ms 11356 KB Output is correct
3 Correct 1404 ms 12372 KB Output is correct
4 Execution timed out 2053 ms 14136 KB Time limit exceeded
5 Execution timed out 2066 ms 40780 KB Time limit exceeded
6 Correct 22 ms 11384 KB Output is correct
7 Correct 165 ms 11576 KB Output is correct
8 Execution timed out 2069 ms 14200 KB Time limit exceeded
9 Execution timed out 2090 ms 14980 KB Time limit exceeded
10 Correct 399 ms 12012 KB Output is correct
11 Execution timed out 2067 ms 15100 KB Time limit exceeded
12 Execution timed out 2056 ms 12424 KB Time limit exceeded
13 Execution timed out 2059 ms 32580 KB Time limit exceeded
14 Execution timed out 2066 ms 12496 KB Time limit exceeded
15 Execution timed out 2035 ms 16832 KB Time limit exceeded
16 Correct 22 ms 11412 KB Output is correct
17 Correct 1149 ms 12320 KB Output is correct
18 Execution timed out 2021 ms 12392 KB Time limit exceeded
19 Execution timed out 2033 ms 12784 KB Time limit exceeded
20 Execution timed out 2048 ms 12564 KB Time limit exceeded
21 Execution timed out 2021 ms 15172 KB Time limit exceeded
22 Execution timed out 2076 ms 16684 KB Time limit exceeded
23 Execution timed out 2028 ms 42136 KB Time limit exceeded
24 Correct 18 ms 11332 KB Output is correct
25 Correct 405 ms 11724 KB Output is correct
26 Execution timed out 2043 ms 12116 KB Time limit exceeded
27 Execution timed out 2017 ms 12920 KB Time limit exceeded
28 Execution timed out 2077 ms 20112 KB Time limit exceeded
29 Correct 842 ms 11968 KB Output is correct
30 Execution timed out 2058 ms 12260 KB Time limit exceeded
31 Execution timed out 2096 ms 12756 KB Time limit exceeded
32 Execution timed out 2009 ms 23144 KB Time limit exceeded
33 Correct 19 ms 11340 KB Output is correct
34 Correct 16 ms 11340 KB Output is correct
35 Correct 1833 ms 12284 KB Output is correct
36 Execution timed out 2074 ms 12232 KB Time limit exceeded
37 Execution timed out 2044 ms 12588 KB Time limit exceeded
38 Execution timed out 2077 ms 13124 KB Time limit exceeded
39 Correct 17 ms 11340 KB Output is correct
40 Correct 425 ms 11704 KB Output is correct
41 Correct 1565 ms 12012 KB Output is correct
42 Execution timed out 2068 ms 12096 KB Time limit exceeded
43 Execution timed out 2080 ms 12016 KB Time limit exceeded
44 Execution timed out 2087 ms 12172 KB Time limit exceeded
45 Execution timed out 2079 ms 12752 KB Time limit exceeded
46 Execution timed out 2017 ms 12920 KB Time limit exceeded
47 Execution timed out 2076 ms 24860 KB Time limit exceeded