Submission #1139819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139819		SmuggingSpun	Bubble Sort 2 (JOI18_bubblesort2)	C++20	38 / 100	6233 ms	664 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
vector<int>countScans(vector<int>a, vector<int>x, vector<int>v){
	int n = a.size(), q = x.size();
	vector<int>ans(q, 0);
	if(n <= 2000 && q <= 2000){
		for(int _i = 0; _i < q; _i++){
			a[x[_i]] = v[_i];
			vector<int>A = a;
			while(true){
				bool swapped = false;
				for(int i = 1; i < n; i++){
					if(A[i - 1] > A[i]){
						swap(A[i - 1], A[i]);
						swapped = true;
					}
				}
				if(!swapped){
					break;
				}
				ans[_i]++;
			}
		}
	}
	else if(n <= 8000 && q <= 8000){
		vector<int>p(n);
		iota(p.begin(), p.end(), 0);
		for(int _i = 0; _i < q; _i++){
			a[x[_i]] = v[_i];
			sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
				return a[i] < a[j] || (a[i] == a[j] && i < j);	
			});
			for(int i = 0; i < n; i++){
				maximize(ans[_i], p[i] - i);
			}
		}
	}
	return ans;
}

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