Submission #363203

#	Time	Username	Problem	Language	Result	Execution time	Memory
363203		r57shell	Bubble Sort 2 (JOI18_bubblesort2)	C++14	17 / 100	9092 ms	1772 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>

using namespace std;

static int stupid(vector<int> A)
{
	int res = 0;
	int n = A.size();
	while (true)
	{
		bool was = false;
		for (int i = 1; i < n; ++i)
		{
			if (A[i-1] > A[i])
			{
				swap(A[i-1], A[i]);
				was = true;
			}
		}
		if (was)
			++res;
		else
			break;
	}
	return res;
}

static int get(vector<int> &f, int x)
{
	int res = 0;
	for (; x >= 0; x = (x&(x+1))-1)
		res += f[x];
	return res;
}

static void add(vector<int> &f, int x, int v)
{
	for (; x < f.size(); x |= (x+1))
		f[x] += v;
}

static int stupid1(vector<int> A)
{
	int n = A.size();
	int res = 0;
	for (int i = 1; i < n; ++i)
	{
		int c = 0;
		for (int j = 0; j < i; ++j)
			if (A[i] < A[j])
				++c;
		res = max(res, c);
	}
	return res;
}

static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
{
	int n = A.size();
	int res = 0;
	vector<int> idx(A.size());
	for (int i = 0; i < n; ++i)
	{
		int id = lower_bound(all.begin(), all.end(), A[i]) - all.begin();
		idx[i] = id;
		//printf("%d %d\n", id, i - get(F, id));
		res = max(res, i - get(F, id));
		add(F, id, 1);
	}
	for (int i = 0; i < n; ++i)
		add(F, idx[i], -1);
	return res;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	vector<int> all(N + Q);
	for (int i = 0; i < N; ++i)
		all[i] = A[i];
	for (int i = 0; i < Q; ++i)
		all[N+i] = V[i];
	sort(all.begin(), all.end());
	vector<int>::iterator z = unique(all.begin(), all.end());
	all.resize(z - all.begin());
	/*for (int j = 0; j < all.size(); ++j)
		printf("%d ", all[j]);
	printf("\n");*/
	vector<int> F(all.size());
	for (int j = 0; j < Q; j++)
	{
		A[X[j]] = V[j];
		answer[j] = smart(A, F, all);
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:39:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (; x < f.size(); x |= (x+1))
      |         ~~^~~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:43:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
   43 | static int stupid1(vector<int> A)
      |            ^~~~~~~
bubblesort2.cpp:6:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
    6 | static int stupid(vector<int> A)
      |            ^~~~~~

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