oj.uz

Submission #884001

# Submission time Handle Problem Language Result Execution time Memory
884001 2023-12-06T14:07:15 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 3048 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2392 KB Output is correct
2 Correct 654 ms 2644 KB Output is correct
3 Correct 8183 ms 3048 KB Output is correct
4 Correct 8244 ms 2556 KB Output is correct
5 Correct 4034 ms 2644 KB Output is correct
6 Correct 618 ms 2560 KB Output is correct
7 Correct 1552 ms 2808 KB Output is correct
8 Correct 2357 ms 2572 KB Output is correct
9 Correct 4120 ms 2648 KB Output is correct
10 Correct 6584 ms 2812 KB Output is correct
11 Correct 6587 ms 2548 KB Output is correct
12 Correct 6596 ms 2644 KB Output is correct
13 Correct 6556 ms 2552 KB Output is correct
14 Correct 6577 ms 2556 KB Output is correct
15 Correct 6607 ms 2556 KB Output is correct
16 Correct 6635 ms 2804 KB Output is correct
17 Correct 6610 ms 2396 KB Output is correct
18 Correct 6594 ms 2552 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2392 KB Output is correct
2 Correct 654 ms 2644 KB Output is correct
3 Correct 8183 ms 3048 KB Output is correct
4 Correct 8244 ms 2556 KB Output is correct
5 Correct 4034 ms 2644 KB Output is correct
6 Correct 618 ms 2560 KB Output is correct
7 Correct 1552 ms 2808 KB Output is correct
8 Correct 2357 ms 2572 KB Output is correct
9 Correct 4120 ms 2648 KB Output is correct
10 Correct 6584 ms 2812 KB Output is correct
11 Correct 6587 ms 2548 KB Output is correct
12 Correct 6596 ms 2644 KB Output is correct
13 Correct 6556 ms 2552 KB Output is correct
14 Correct 6577 ms 2556 KB Output is correct
15 Correct 6607 ms 2556 KB Output is correct
16 Correct 6635 ms 2804 KB Output is correct
17 Correct 6610 ms 2396 KB Output is correct
18 Correct 6594 ms 2552 KB Output is correct
19 Execution timed out 9051 ms 2732 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9022 ms 2804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2392 KB Output is correct
2 Correct 654 ms 2644 KB Output is correct
3 Correct 8183 ms 3048 KB Output is correct
4 Correct 8244 ms 2556 KB Output is correct
5 Correct 4034 ms 2644 KB Output is correct
6 Correct 618 ms 2560 KB Output is correct
7 Correct 1552 ms 2808 KB Output is correct
8 Correct 2357 ms 2572 KB Output is correct
9 Correct 4120 ms 2648 KB Output is correct
10 Correct 6584 ms 2812 KB Output is correct
11 Correct 6587 ms 2548 KB Output is correct
12 Correct 6596 ms 2644 KB Output is correct
13 Correct 6556 ms 2552 KB Output is correct
14 Correct 6577 ms 2556 KB Output is correct
15 Correct 6607 ms 2556 KB Output is correct
16 Correct 6635 ms 2804 KB Output is correct
17 Correct 6610 ms 2396 KB Output is correct
18 Correct 6594 ms 2552 KB Output is correct
19 Execution timed out 9051 ms 2732 KB Time limit exceeded
20 Halted 0 ms 0 KB -