Submission #364436

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

bubblesort2

#include "bubblesort2.h"
#include <set>
#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;
	for (int i = 0; i < n; ++i)
	{
		res = max(res, i - get(F, A[i]));
		add(F, A[i], 1);
	}
	for (int i = 0; i < n; ++i)
		add(F, A[i], -1);
	return res;
}

static int smart1(const vector<int> &A)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int j = 0; j < i; ++j)
				if (A[i] < A[j])
					++c;
			res = max(res, c);
		}
	}
	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);
	for (int j = 0; j < Q; ++j)
	{
		A[X[j]] = V[j];
		answer[j] = smart1(A);
	}
	return answer;
	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");*/
	if (all.back() <= 100)
	{
		vector<int> T[101];
		for (int x = 0; x <= 100; ++x)
			T[x].resize(2*N);
		for (int j = 0; j < N; ++j) 
			for (int x = A[j] - 1; x >= 0; --x)
				add(T[x], j, 1);
		set<int> pos[101];
		for (int j = 0; j < N; ++j) 
			pos[A[j]].insert(-j);
		for (int j = 0; j < Q; j++)
		{
			int p = X[j];
			for (int x = A[p] - 1; x >= 0; --x)
			{
				add(T[x], p, -1);
			}
			pos[A[p]].erase(-p);
			A[p] = V[j];
			for (int x = V[j] - 1; x >= 0; --x)
				add(T[x], p, 1);
			pos[V[j]].insert(-p);
			int ans = 0;
			for (int x = 0; x <= 100; ++x)
				if (pos[x].size())
				{
					ans = max(ans, get(T[x], -*(pos[x].begin())));
				}
			answer[j] = ans;
		}
	}
	else
	{
		for (int j = 0; j < N; j++)
			A[j] = lower_bound(all.begin(), all.end(), A[j]) - all.begin();
		for (int j = 0; j < Q; j++)
			V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();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:40:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (; x < f.size(); x |= (x+1))
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:151:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  151 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:152:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  152 |    V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
      |                                                                   ^~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:44:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
   44 | static int stupid1(vector<int> A)
      |            ^~~~~~~
bubblesort2.cpp:7:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
    7 | static int stupid(vector<int> A)
      |            ^~~~~~

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