oj.uz

Submission #1106403

# Submission time Handle Problem Language Result Execution time Memory
1106403 2024-10-30T09:19:50 Z VinhLuu Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 6992 KB 
#include <bits/stdc++.h>
#define ll long long
#include "bubblesort2.h"
using namespace std;

const int N = 1e6 + 5;

int n, q, a[N], _x[N], _y[N], kq[N];

namespace sub1{
  int b[N];
  vector<int> solve(){
    vector<int> ans;
    for(int k = 1; k <= q; k ++){
      int x = _x[k], y = _y[k];
      a[x] = y;
      int cnt = 0;
      for(int i = 1; i <= n; i ++) b[i] = a[i];
      while(true){
        bool ff = true;
        for(int i = 1; i < n; i ++) if(b[i] > b[i + 1]){
          swap(b[i], b[i + 1]);
          ff = false;
        }
        if(ff) break;

        cnt++;
      }
      ans.push_back(cnt);
    }
    return ans;
  }
}

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

  q = X.size();

  for(int k = 0; k < q; k ++){
    _x[k + 1] = X[k] + 1, _y[k + 1] = V[k];
  }

  return sub1 :: solve();


  int ans = 0;

	std::vector<int> answer(q);
	for(int j = 0; j < q; j ++) {
		answer[j] = kq[j];
	}
	return answer;
}

//#define LOCAL

#ifdef LOCAL

int _n, _q;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

	cin >> _n >> _q;

	std::vector<int> A(_n);
  for(int i = 0; i < _n; i ++)
    cin >> A[i];

	std::vector<int> X(_q),V(_q);
	for(int j = 0; j < _q ; j++){
		cin >> X[j] >> V[j];
	}


	std::vector<int> res=countScans(A,X,V);

	for(int j=0;j<int(res.size());j++)
		cout << res[j] << "\n";
}

/*
4 2
1 2 3 4
0 3
2 1
*/

#endif // LOCAL

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:48:7: warning: unused variable 'ans' [-Wunused-variable]
   48 |   int ans = 0;
      |       ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6480 KB Output is correct
2 Correct 443 ms 6480 KB Output is correct
3 Correct 6249 ms 6696 KB Output is correct
4 Correct 6129 ms 6712 KB Output is correct
5 Correct 2630 ms 6480 KB Output is correct
6 Correct 358 ms 6480 KB Output is correct
7 Correct 890 ms 6480 KB Output is correct
8 Correct 1396 ms 6716 KB Output is correct
9 Correct 2595 ms 6708 KB Output is correct
10 Correct 3029 ms 6700 KB Output is correct
11 Correct 3057 ms 6736 KB Output is correct
12 Correct 2960 ms 6700 KB Output is correct
13 Correct 3066 ms 6700 KB Output is correct
14 Correct 2966 ms 6704 KB Output is correct
15 Correct 3089 ms 6688 KB Output is correct
16 Correct 3042 ms 6684 KB Output is correct
17 Correct 2988 ms 6700 KB Output is correct
18 Correct 3044 ms 6684 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6480 KB Output is correct
2 Correct 443 ms 6480 KB Output is correct
3 Correct 6249 ms 6696 KB Output is correct
4 Correct 6129 ms 6712 KB Output is correct
5 Correct 2630 ms 6480 KB Output is correct
6 Correct 358 ms 6480 KB Output is correct
7 Correct 890 ms 6480 KB Output is correct
8 Correct 1396 ms 6716 KB Output is correct
9 Correct 2595 ms 6708 KB Output is correct
10 Correct 3029 ms 6700 KB Output is correct
11 Correct 3057 ms 6736 KB Output is correct
12 Correct 2960 ms 6700 KB Output is correct
13 Correct 3066 ms 6700 KB Output is correct
14 Correct 2966 ms 6704 KB Output is correct
15 Correct 3089 ms 6688 KB Output is correct
16 Correct 3042 ms 6684 KB Output is correct
17 Correct 2988 ms 6700 KB Output is correct
18 Correct 3044 ms 6684 KB Output is correct
19 Execution timed out 9065 ms 6948 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 9054 ms 6992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6480 KB Output is correct
2 Correct 443 ms 6480 KB Output is correct
3 Correct 6249 ms 6696 KB Output is correct
4 Correct 6129 ms 6712 KB Output is correct
5 Correct 2630 ms 6480 KB Output is correct
6 Correct 358 ms 6480 KB Output is correct
7 Correct 890 ms 6480 KB Output is correct
8 Correct 1396 ms 6716 KB Output is correct
9 Correct 2595 ms 6708 KB Output is correct
10 Correct 3029 ms 6700 KB Output is correct
11 Correct 3057 ms 6736 KB Output is correct
12 Correct 2960 ms 6700 KB Output is correct
13 Correct 3066 ms 6700 KB Output is correct
14 Correct 2966 ms 6704 KB Output is correct
15 Correct 3089 ms 6688 KB Output is correct
16 Correct 3042 ms 6684 KB Output is correct
17 Correct 2988 ms 6700 KB Output is correct
18 Correct 3044 ms 6684 KB Output is correct
19 Execution timed out 9065 ms 6948 KB Time limit exceeded
20 Halted 0 ms 0 KB -