Submission #1139825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139825		SmuggingSpun	Bubble Sort 2 (JOI18_bubblesort2)	C++20	60 / 100	7806 ms	4164 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);
			}
		}
	}
	else if(n <= 50000 && q <= 50000 && *max_element(a.begin(), a.end()) <= 100 && *max_element(v.begin(), v.end()) <= 100){
		vector<set<int>>pos(101);
		for(int i = 0; i < n; i++){
			pos[a[i]].insert(i);
		}
		for(int _i = 0; _i < q; _i++){
			pos[a[x[_i]]].erase(x[_i]);
			pos[a[x[_i]] = v[_i]].insert(x[_i]);
			for(int i = 1, cnt = 0; i < 101; i++){
				if(!pos[i].empty()){
					maximize(ans[_i], *pos[i].rbegin() - (cnt += pos[i].size()) + 1);
				}
			} 
		}		
	}
	else{
		
	}
	return ans;
}

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