Submission #881558

#	Time	Username	Problem	Language	Result	Execution time	Memory
881558		m_bezrutchka	Bubble Sort 2 (JOI18_bubblesort2)	C++14	17 / 100	8872 ms	1060 KiB

bubblesort2

#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 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40