oj.uz

Submission #509797

# Submission time Handle Problem Language Result Execution time Memory
509797 2022-01-14T10:00:11 Z 600Mihnea Archery (IOI09_archery) C++17
39 / 100
 2000 ms 34952 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;
  }
  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 11212 KB Output is correct
2 Correct 7 ms 11212 KB Output is correct
3 Correct 8 ms 11212 KB Output is correct
4 Incorrect 31 ms 11596 KB Output isn't correct
5 Correct 6 ms 11296 KB Output is correct
6 Correct 17 ms 11212 KB Output is correct

Subtask #2
34.0 / 94.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11264 KB Output isn't correct
2 Incorrect 7 ms 11212 KB Output isn't correct
3 Incorrect 20 ms 11480 KB Output isn't correct
4 Incorrect 236 ms 13360 KB Output isn't correct
5 Execution timed out 2077 ms 33872 KB Time limit exceeded
6 Correct 6 ms 11212 KB Output is correct
7 Correct 12 ms 11412 KB Output is correct
8 Correct 216 ms 13144 KB Output is correct
9 Correct 329 ms 14032 KB Output is correct
10 Correct 20 ms 11340 KB Output is correct
11 Incorrect 368 ms 14136 KB Output isn't correct
12 Incorrect 31 ms 11596 KB Output isn't correct
13 Execution timed out 2085 ms 28160 KB Time limit exceeded
14 Incorrect 69 ms 11852 KB Output isn't correct
15 Incorrect 629 ms 15800 KB Output isn't correct
16 Incorrect 8 ms 11276 KB Output isn't correct
17 Incorrect 20 ms 11472 KB Output isn't correct
18 Incorrect 26 ms 11468 KB Output isn't correct
19 Correct 47 ms 11768 KB Output is correct
20 Correct 69 ms 11944 KB Output is correct
21 Incorrect 369 ms 14104 KB Output isn't correct
22 Correct 503 ms 15476 KB Output is correct
23 Execution timed out 2074 ms 34952 KB Time limit exceeded
24 Correct 19 ms 11304 KB Output is correct
25 Correct 408 ms 11340 KB Output is correct
26 Execution timed out 2078 ms 11468 KB Time limit exceeded
27 Execution timed out 2084 ms 12436 KB Time limit exceeded
28 Execution timed out 2086 ms 18116 KB Time limit exceeded
29 Correct 839 ms 11372 KB Output is correct
30 Execution timed out 2095 ms 11468 KB Time limit exceeded
31 Execution timed out 2088 ms 12364 KB Time limit exceeded
32 Execution timed out 2083 ms 20760 KB Time limit exceeded
33 Correct 18 ms 11312 KB Output is correct
34 Correct 16 ms 11308 KB Output is correct
35 Correct 1836 ms 11392 KB Output is correct
36 Execution timed out 2080 ms 11340 KB Time limit exceeded
37 Execution timed out 2088 ms 12108 KB Time limit exceeded
38 Execution timed out 2077 ms 12620 KB Time limit exceeded
39 Correct 16 ms 11312 KB Output is correct
40 Correct 422 ms 11340 KB Output is correct
41 Correct 1537 ms 11392 KB Output is correct
42 Execution timed out 2081 ms 11340 KB Time limit exceeded
43 Execution timed out 2084 ms 11468 KB Time limit exceeded
44 Execution timed out 2075 ms 11724 KB Time limit exceeded
45 Execution timed out 2092 ms 12292 KB Time limit exceeded
46 Execution timed out 2096 ms 12492 KB Time limit exceeded
47 Execution timed out 2098 ms 22212 KB Time limit exceeded