oj.uz

Submission #104897

# Submission time Handle Problem Language Result Execution time Memory
104897 2019-04-09T13:47:45 Z WLZ Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 9968 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, a;
  cin >> n >> a;
  vector< pair<int, int> > d(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i].first;
    d[i].second = i + 1;
  }
  sort(d.rbegin(), d.rend());
  vector<int> top10;
  vector<int> v;
  for (int i = 0; i < min(10, n); i++) {
    top10.push_back(d[i].second);
  }
  for (int i = n; i >= 10; i--) {
    v.push_back(d[i].second);
  }
  int q;
  cin >> q;
  while (q--) {
    char t;
    cin >> t;
    if (t == 'F') {
      int b;
      cin >> b;
      int cur = n;
      vector<int> num(n + 1, -1);
      for (auto& x : top10) {
        if (num[x] == -1) {
          num[x] = cur--;
        }
      }
      for (int i = (int) v.size() - 1; i >= 0; i--) {
        if (num[v[i]] == -1) {
          num[v[i]] = cur--;
        }
      }
      priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
      pq.push({num[a], a});
      int cnt = 0;
      while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        num[x] = -1;
        if (x == b) {
          cout << cnt << '\n';
        }
        cnt++;
        if (x > 1 && num[x - 1] != -1) {
          pq.push({num[x - 1], x - 1});
        }
        if (x < n && num[x + 1] != -1) {
          pq.push({num[x + 1], x + 1});
        }
      }
    } else {
      int i, e;
      cin >> i >> e;
      auto it = top10.begin();
      for (int j = 0; j < e - 1; j++) {
        it = next(it);
      }
      top10.insert(it, i);
      v.push_back(top10.back());
      top10.pop_back();
    }
  }
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 331 ms 7088 KB Output isn't correct
2 Correct 251 ms 6964 KB Output is correct
3 Correct 306 ms 7140 KB Output is correct
4 Correct 340 ms 7300 KB Output is correct
5 Incorrect 519 ms 7552 KB Output isn't correct
6 Correct 478 ms 9856 KB Output is correct
7 Correct 430 ms 9668 KB Output is correct
8 Correct 433 ms 9968 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 2812 KB Time limit exceeded
2 Execution timed out 2050 ms 2932 KB Time limit exceeded
3 Execution timed out 2048 ms 2812 KB Time limit exceeded
4 Incorrect 3 ms 384 KB Output isn't correct
5 Execution timed out 2047 ms 6220 KB Time limit exceeded
6 Execution timed out 2031 ms 6256 KB Time limit exceeded
7 Execution timed out 2024 ms 6256 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 1252 KB Time limit exceeded
2 Execution timed out 2032 ms 1316 KB Time limit exceeded
3 Execution timed out 2097 ms 1824 KB Time limit exceeded
4 Execution timed out 2096 ms 1952 KB Time limit exceeded
5 Execution timed out 2008 ms 1592 KB Time limit exceeded
6 Execution timed out 2055 ms 2292 KB Time limit exceeded
7 Execution timed out 2039 ms 1168 KB Time limit exceeded
8 Execution timed out 2040 ms 3812 KB Time limit exceeded
9 Execution timed out 2023 ms 6128 KB Time limit exceeded
10 Execution timed out 2017 ms 1364 KB Time limit exceeded
11 Execution timed out 2037 ms 1408 KB Time limit exceeded
12 Execution timed out 2058 ms 5088 KB Time limit exceeded
13 Execution timed out 2063 ms 6256 KB Time limit exceeded