제출 #1347274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1347274		jahongir	Bubble Sort 2 (JOI18_bubblesort2)	C++20	17 / 100	9092 ms	1100 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int N = (int) A.size();
	int Q = (int) X.size();

	vector<int> res(Q,0);
	
	for(int t = 0; t < Q; t++){
		A[X[t]] = V[t];

		vector<pair<int,int>> vec(N);
		for(int i = 0; i < N; i++)
			vec[i] = {A[i],i};

		sort(vec.begin(),vec.end());
			
		vector<int> ind(N+1);
		ind[N] = N;

		for(int i = 0; i < N; i++)
			ind[i] = vec[i].second;

		for(; ;){
			vector<int> tmp(N+1);
			tmp[N] = N;
			
			int mn = N;
			for(int i = N-1; i >= 0; i--){
				tmp[i] = max(ind[i],mn)-1;
				mn = min(mn,ind[i]);
			}
			
			if(tmp==ind) break;
			res[t]++;
			ind = tmp;
		}
	}

	return res;
}

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