oj.uz

Submission #881558

# Submission time Handle Problem Language Result Execution time Memory
881558 2023-12-01T13:02:48 Z m_bezrutchka Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 8872 ms 1060 KB 
#include <bits/stdc++.h>
using namespace std;

const int ST1_LIM = 2000;
const int ST2_LIM = 8000;
const int ST3_LIM = 50000;
int n, q;
vector <int> cur;
vector <int> v;
vector <int> ans;

int bubble_sort() {
  cur.resize(n);
  for (int i = 0; i < n; i++) {
    cur[i] = v[i];
  }
  int num_swaps = 0;
  while (true) {
    bool saw_new_swap = false;
    for (int i = 0; i < n - 1; i++) {
      if (cur[i] > cur[i + 1]) {
        saw_new_swap = true;
        swap(cur[i], cur[i + 1]);
      }
    }
    if (saw_new_swap) {
      num_swaps++;
    } else {
      break;
    }
  }
  return num_swaps;
}

vector<int> solve_st1(vector<int> A, vector<int> X, vector<int> V) {
  for (int i = 0; i < q; i++) {
    v[X[i]] = V[i];
    ans.push_back(bubble_sort());
  }
  return ans;
}

vector<int> solve_st2(vector<int> A, vector<int> X, vector<int> V) {
  return ans;
}

vector<int> solve_st3(vector<int> A, vector<int> X, vector<int> V) {
  return ans;
}

vector<int> solve_st4(vector<int> A, vector<int> X, vector<int> V) {
  return ans;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
  n = (int) A.size();
  q = (int) X.size();
  v.resize(n);
  for (int i = 0; i < n; i++) {
    v[i] = A[i];
  }
  if (max(n, q) <= ST1_LIM) {
    return solve_st1(A, X, V);
  } else if (max(n, q) <= ST2_LIM) {
    return solve_st2(A, X, V);
  } else if (max(n, q) <= ST3_LIM) {
    return solve_st3(A, X, V);
  } else {
    return solve_st4(A, X, V);
  }
}

/* int main() {
  vector<int> A;
  vector<int> X;
  vector<int> V;

  int _n, _q;
  cin >> _n >> _q;
  A.resize(_n);
  X.resize(_q);
  V.resize(_q);
  for (int i = 0; i < _n; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < _q; i++) {
    cin >> X[i] >> V[i];
  }

  vector<int> S = countScans(A, X, V);
  for (int i = 0; i < _q; i++) {
    cout << S[i] << "\n";
  }

  return 0;
} */

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 448 KB Output is correct
2 Correct 628 ms 464 KB Output is correct
3 Correct 8872 ms 600 KB Output is correct
4 Correct 8582 ms 1060 KB Output is correct
5 Correct 3722 ms 808 KB Output is correct
6 Correct 610 ms 348 KB Output is correct
7 Correct 1472 ms 600 KB Output is correct
8 Correct 2244 ms 800 KB Output is correct
9 Correct 3804 ms 568 KB Output is correct
10 Correct 6572 ms 596 KB Output is correct
11 Correct 6573 ms 552 KB Output is correct
12 Correct 6576 ms 556 KB Output is correct
13 Correct 6684 ms 792 KB Output is correct
14 Correct 6600 ms 552 KB Output is correct
15 Correct 6538 ms 548 KB Output is correct
16 Correct 6556 ms 536 KB Output is correct
17 Correct 6589 ms 800 KB Output is correct
18 Correct 6477 ms 1052 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 448 KB Output is correct
2 Correct 628 ms 464 KB Output is correct
3 Correct 8872 ms 600 KB Output is correct
4 Correct 8582 ms 1060 KB Output is correct
5 Correct 3722 ms 808 KB Output is correct
6 Correct 610 ms 348 KB Output is correct
7 Correct 1472 ms 600 KB Output is correct
8 Correct 2244 ms 800 KB Output is correct
9 Correct 3804 ms 568 KB Output is correct
10 Correct 6572 ms 596 KB Output is correct
11 Correct 6573 ms 552 KB Output is correct
12 Correct 6576 ms 556 KB Output is correct
13 Correct 6684 ms 792 KB Output is correct
14 Correct 6600 ms 552 KB Output is correct
15 Correct 6538 ms 548 KB Output is correct
16 Correct 6556 ms 536 KB Output is correct
17 Correct 6589 ms 800 KB Output is correct
18 Correct 6477 ms 1052 KB Output is correct
19 Incorrect 2 ms 856 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 448 KB Output is correct
2 Correct 628 ms 464 KB Output is correct
3 Correct 8872 ms 600 KB Output is correct
4 Correct 8582 ms 1060 KB Output is correct
5 Correct 3722 ms 808 KB Output is correct
6 Correct 610 ms 348 KB Output is correct
7 Correct 1472 ms 600 KB Output is correct
8 Correct 2244 ms 800 KB Output is correct
9 Correct 3804 ms 568 KB Output is correct
10 Correct 6572 ms 596 KB Output is correct
11 Correct 6573 ms 552 KB Output is correct
12 Correct 6576 ms 556 KB Output is correct
13 Correct 6684 ms 792 KB Output is correct
14 Correct 6600 ms 552 KB Output is correct
15 Correct 6538 ms 548 KB Output is correct
16 Correct 6556 ms 536 KB Output is correct
17 Correct 6589 ms 800 KB Output is correct
18 Correct 6477 ms 1052 KB Output is correct
19 Incorrect 2 ms 856 KB Output isn't correct
20 Halted 0 ms 0 KB -