Submission #884001

#	Time	Username	Problem	Language	Result	Execution time	Memory
884001		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9051 ms	3048 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 5e5+5;

struct Query {
   int pos, val;
};

int n, m;
int a[NMAX];
Query q[NMAX];

int bubble_sort(vector<int> a) {
   bool ok = 1;
   int cnt = 0;
   while (ok) {
      ok = 0;
      for (int i = 1; i < n; i++) {
         if (a[i - 1] > a[i]) {
            swap(a[i - 1], a[i]);
            ok = 1;
         }
      }
      cnt += ok;
   }
   return cnt;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V) {
   n = sz(A);
   m = sz(X);
   for (int i = 0; i < n; i++)
      a[i + 1] = A[i];
   for (int i = 0; i < m; i++)
      q[i + 1] = { X[i], V[i] };

   vector<int> ans;

   for (int i = 0; i < sz(X); i++) {
      A[X[i]] = V[i];
      ans.push_back(bubble_sort(A));
   }

   return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40