oj.uz

Submission #852924

# Submission time Handle Problem Language Result Execution time Memory
852924 2023-09-23T07:36:06 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
39 / 100
 8537 ms 4180 KB 
// by me
#include "bubblesort2.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
	int Q = X.size();
	int N = A.size();
	vector<int> ans(Q, 0);
	if(N <= 2000){
		for(int i = 0; i < Q; i++){
			A[X[i]] = V[i];
			auto f = A;
			while(!is_sorted(all(f))){
				ans[i]++;
				for(int i = 1; i < f.size(); i++){
					if(f[i] < f[i - 1]) swap(f[i], f[i - 1]);
				}
			}
	    }
		return ans;
	}
	vector<set<int>> f(101);
	for(int i = 0; i < N; i++){
		f[A[i]].insert(i);
	}
	for(int i = 0; i < Q; i++){
		f[A[X[i]]].erase(X[i]);
		A[X[i]] = V[i];
		f[A[X[i]]].insert(X[i]);
		int x = 0;
		for(auto &st : f){
			if(st.empty()) continue;
			x += st.size();
			int mx = *st.rbegin();
			ans[i] = max(ans[i], mx - x + 1);
		}
	}
	return ans;
}

//
/*
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();

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

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

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

	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}
//*/
// by me

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 1; i < f.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 424 KB Output is correct
2 Correct 636 ms 436 KB Output is correct
3 Correct 8537 ms 472 KB Output is correct
4 Correct 8414 ms 476 KB Output is correct
5 Correct 3875 ms 468 KB Output is correct
6 Correct 683 ms 472 KB Output is correct
7 Correct 1602 ms 472 KB Output is correct
8 Correct 2333 ms 468 KB Output is correct
9 Correct 3910 ms 468 KB Output is correct
10 Correct 6568 ms 472 KB Output is correct
11 Correct 6633 ms 472 KB Output is correct
12 Correct 6559 ms 468 KB Output is correct
13 Correct 6590 ms 476 KB Output is correct
14 Correct 6546 ms 468 KB Output is correct
15 Correct 6561 ms 468 KB Output is correct
16 Correct 6552 ms 488 KB Output is correct
17 Correct 6616 ms 476 KB Output is correct
18 Correct 6528 ms 468 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 424 KB Output is correct
2 Correct 636 ms 436 KB Output is correct
3 Correct 8537 ms 472 KB Output is correct
4 Correct 8414 ms 476 KB Output is correct
5 Correct 3875 ms 468 KB Output is correct
6 Correct 683 ms 472 KB Output is correct
7 Correct 1602 ms 472 KB Output is correct
8 Correct 2333 ms 468 KB Output is correct
9 Correct 3910 ms 468 KB Output is correct
10 Correct 6568 ms 472 KB Output is correct
11 Correct 6633 ms 472 KB Output is correct
12 Correct 6559 ms 468 KB Output is correct
13 Correct 6590 ms 476 KB Output is correct
14 Correct 6546 ms 468 KB Output is correct
15 Correct 6561 ms 468 KB Output is correct
16 Correct 6552 ms 488 KB Output is correct
17 Correct 6616 ms 476 KB Output is correct
18 Correct 6528 ms 468 KB Output is correct
19 Runtime error 2 ms 860 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1884 KB Output is correct
2 Correct 29 ms 3100 KB Output is correct
3 Correct 56 ms 4176 KB Output is correct
4 Correct 58 ms 4160 KB Output is correct
5 Correct 53 ms 4112 KB Output is correct
6 Correct 53 ms 3932 KB Output is correct
7 Correct 53 ms 4144 KB Output is correct
8 Correct 54 ms 4148 KB Output is correct
9 Correct 58 ms 3932 KB Output is correct
10 Correct 47 ms 3928 KB Output is correct
11 Correct 47 ms 3932 KB Output is correct
12 Correct 47 ms 3932 KB Output is correct
13 Correct 44 ms 3932 KB Output is correct
14 Correct 44 ms 4144 KB Output is correct
15 Correct 44 ms 4180 KB Output is correct
16 Correct 40 ms 3928 KB Output is correct
17 Correct 39 ms 4104 KB Output is correct
18 Correct 40 ms 3928 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 424 KB Output is correct
2 Correct 636 ms 436 KB Output is correct
3 Correct 8537 ms 472 KB Output is correct
4 Correct 8414 ms 476 KB Output is correct
5 Correct 3875 ms 468 KB Output is correct
6 Correct 683 ms 472 KB Output is correct
7 Correct 1602 ms 472 KB Output is correct
8 Correct 2333 ms 468 KB Output is correct
9 Correct 3910 ms 468 KB Output is correct
10 Correct 6568 ms 472 KB Output is correct
11 Correct 6633 ms 472 KB Output is correct
12 Correct 6559 ms 468 KB Output is correct
13 Correct 6590 ms 476 KB Output is correct
14 Correct 6546 ms 468 KB Output is correct
15 Correct 6561 ms 468 KB Output is correct
16 Correct 6552 ms 488 KB Output is correct
17 Correct 6616 ms 476 KB Output is correct
18 Correct 6528 ms 468 KB Output is correct
19 Runtime error 2 ms 860 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -