oj.uz

Submission #509798

# Submission time Handle Problem Language Result Execution time Memory
509798 2022-01-14T10:02:29 Z 600Mihnea Archery (IOI09_archery) C++17
64 / 100
 2000 ms 34840 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];


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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11212 KB Output is correct
2 Correct 6 ms 11212 KB Output is correct
3 Correct 9 ms 11212 KB Output is correct
4 Correct 72 ms 11604 KB Output is correct
5 Correct 6 ms 11212 KB Output is correct
6 Correct 17 ms 11304 KB Output is correct

Subtask #2
58.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 8 ms 11320 KB Output is correct
3 Correct 40 ms 11468 KB Output is correct
4 Correct 610 ms 13404 KB Output is correct
5 Execution timed out 2080 ms 33804 KB Time limit exceeded
6 Correct 8 ms 11320 KB Output is correct
7 Correct 13 ms 11412 KB Output is correct
8 Correct 214 ms 13192 KB Output is correct
9 Correct 840 ms 14124 KB Output is correct
10 Correct 20 ms 11340 KB Output is correct
11 Correct 987 ms 14128 KB Output is correct
12 Correct 64 ms 11596 KB Output is correct
13 Execution timed out 2078 ms 28156 KB Time limit exceeded
14 Correct 173 ms 11940 KB Output is correct
15 Correct 1607 ms 15744 KB Output is correct
16 Correct 8 ms 11212 KB Output is correct
17 Correct 37 ms 11468 KB Output is correct
18 Correct 55 ms 11468 KB Output is correct
19 Correct 108 ms 11768 KB Output is correct
20 Correct 165 ms 11948 KB Output is correct
21 Correct 671 ms 14080 KB Output is correct
22 Correct 1502 ms 15512 KB Output is correct
23 Execution timed out 2084 ms 34840 KB Time limit exceeded
24 Correct 19 ms 11212 KB Output is correct
25 Correct 428 ms 11336 KB Output is correct
26 Execution timed out 2072 ms 11468 KB Time limit exceeded
27 Execution timed out 2080 ms 12364 KB Time limit exceeded
28 Execution timed out 2077 ms 18152 KB Time limit exceeded
29 Correct 871 ms 11356 KB Output is correct
30 Execution timed out 2052 ms 11468 KB Time limit exceeded
31 Execution timed out 2078 ms 12364 KB Time limit exceeded
32 Execution timed out 2041 ms 20808 KB Time limit exceeded
33 Correct 22 ms 11212 KB Output is correct
34 Correct 16 ms 11308 KB Output is correct
35 Correct 1913 ms 11388 KB Output is correct
36 Execution timed out 2080 ms 11340 KB Time limit exceeded
37 Execution timed out 2073 ms 12108 KB Time limit exceeded
38 Execution timed out 2085 ms 12584 KB Time limit exceeded
39 Correct 16 ms 11212 KB Output is correct
40 Correct 411 ms 11340 KB Output is correct
41 Correct 1580 ms 11392 KB Output is correct
42 Execution timed out 2078 ms 11340 KB Time limit exceeded
43 Execution timed out 2082 ms 11468 KB Time limit exceeded
44 Execution timed out 2060 ms 11724 KB Time limit exceeded
45 Execution timed out 2076 ms 12364 KB Time limit exceeded
46 Execution timed out 2071 ms 12472 KB Time limit exceeded
47 Execution timed out 2086 ms 22160 KB Time limit exceeded