oj.uz

Submission #364436

# Submission time Handle Problem Language Result Execution time Memory
364436 2021-02-09T07:16:53 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 2284 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 28 ms 364 KB Output is correct
4 Correct 73 ms 492 KB Output is correct
5 Correct 1567 ms 460 KB Output is correct
6 Correct 5594 ms 460 KB Output is correct
7 Correct 7159 ms 460 KB Output is correct
8 Correct 6501 ms 460 KB Output is correct
9 Correct 1075 ms 492 KB Output is correct
10 Correct 2183 ms 492 KB Output is correct
11 Correct 2100 ms 492 KB Output is correct
12 Correct 2088 ms 364 KB Output is correct
13 Correct 2129 ms 452 KB Output is correct
14 Correct 2090 ms 452 KB Output is correct
15 Correct 2154 ms 492 KB Output is correct
16 Correct 2099 ms 452 KB Output is correct
17 Correct 2058 ms 492 KB Output is correct
18 Correct 2076 ms 452 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 28 ms 364 KB Output is correct
4 Correct 73 ms 492 KB Output is correct
5 Correct 1567 ms 460 KB Output is correct
6 Correct 5594 ms 460 KB Output is correct
7 Correct 7159 ms 460 KB Output is correct
8 Correct 6501 ms 460 KB Output is correct
9 Correct 1075 ms 492 KB Output is correct
10 Correct 2183 ms 492 KB Output is correct
11 Correct 2100 ms 492 KB Output is correct
12 Correct 2088 ms 364 KB Output is correct
13 Correct 2129 ms 452 KB Output is correct
14 Correct 2090 ms 452 KB Output is correct
15 Correct 2154 ms 492 KB Output is correct
16 Correct 2099 ms 452 KB Output is correct
17 Correct 2058 ms 492 KB Output is correct
18 Correct 2076 ms 452 KB Output is correct
19 Correct 398 ms 748 KB Output is correct
20 Correct 453 ms 876 KB Output is correct
21 Execution timed out 9010 ms 748 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 620 KB Output is correct
2 Correct 6369 ms 1464 KB Output is correct
3 Execution timed out 9060 ms 2284 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 28 ms 364 KB Output is correct
4 Correct 73 ms 492 KB Output is correct
5 Correct 1567 ms 460 KB Output is correct
6 Correct 5594 ms 460 KB Output is correct
7 Correct 7159 ms 460 KB Output is correct
8 Correct 6501 ms 460 KB Output is correct
9 Correct 1075 ms 492 KB Output is correct
10 Correct 2183 ms 492 KB Output is correct
11 Correct 2100 ms 492 KB Output is correct
12 Correct 2088 ms 364 KB Output is correct
13 Correct 2129 ms 452 KB Output is correct
14 Correct 2090 ms 452 KB Output is correct
15 Correct 2154 ms 492 KB Output is correct
16 Correct 2099 ms 452 KB Output is correct
17 Correct 2058 ms 492 KB Output is correct
18 Correct 2076 ms 452 KB Output is correct
19 Correct 398 ms 748 KB Output is correct
20 Correct 453 ms 876 KB Output is correct
21 Execution timed out 9010 ms 748 KB Time limit exceeded
22 Halted 0 ms 0 KB -