oj.uz

Submission #363238

# Submission time Handle Problem Language Result Execution time Memory
363238 2021-02-05T10:30:15 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 44784 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;
}

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");*/
	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:125:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  125 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:126:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |    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 12 ms 364 KB Output is correct
2 Correct 30 ms 416 KB Output is correct
3 Correct 167 ms 492 KB Output is correct
4 Correct 169 ms 492 KB Output is correct
5 Correct 183 ms 492 KB Output is correct
6 Correct 158 ms 492 KB Output is correct
7 Correct 161 ms 492 KB Output is correct
8 Correct 167 ms 492 KB Output is correct
9 Correct 165 ms 492 KB Output is correct
10 Correct 145 ms 492 KB Output is correct
11 Correct 145 ms 484 KB Output is correct
12 Correct 145 ms 492 KB Output is correct
13 Correct 147 ms 492 KB Output is correct
14 Correct 144 ms 484 KB Output is correct
15 Correct 147 ms 492 KB Output is correct
16 Correct 146 ms 492 KB Output is correct
17 Correct 142 ms 492 KB Output is correct
18 Correct 147 ms 492 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 364 KB Output is correct
2 Correct 30 ms 416 KB Output is correct
3 Correct 167 ms 492 KB Output is correct
4 Correct 169 ms 492 KB Output is correct
5 Correct 183 ms 492 KB Output is correct
6 Correct 158 ms 492 KB Output is correct
7 Correct 161 ms 492 KB Output is correct
8 Correct 167 ms 492 KB Output is correct
9 Correct 165 ms 492 KB Output is correct
10 Correct 145 ms 492 KB Output is correct
11 Correct 145 ms 484 KB Output is correct
12 Correct 145 ms 492 KB Output is correct
13 Correct 147 ms 492 KB Output is correct
14 Correct 144 ms 484 KB Output is correct
15 Correct 147 ms 492 KB Output is correct
16 Correct 146 ms 492 KB Output is correct
17 Correct 142 ms 492 KB Output is correct
18 Correct 147 ms 492 KB Output is correct
19 Correct 2248 ms 828 KB Output is correct
20 Correct 2874 ms 896 KB Output is correct
21 Correct 2814 ms 900 KB Output is correct
22 Correct 2859 ms 1004 KB Output is correct
23 Correct 2581 ms 988 KB Output is correct
24 Correct 2586 ms 876 KB Output is correct
25 Correct 2575 ms 876 KB Output is correct
26 Correct 2574 ms 852 KB Output is correct
27 Correct 2578 ms 876 KB Output is correct
28 Correct 2585 ms 876 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 24044 KB Output is correct
2 Correct 393 ms 35256 KB Output is correct
3 Correct 687 ms 44652 KB Output is correct
4 Correct 689 ms 44656 KB Output is correct
5 Correct 838 ms 44652 KB Output is correct
6 Correct 787 ms 44652 KB Output is correct
7 Correct 913 ms 44780 KB Output is correct
8 Correct 914 ms 44652 KB Output is correct
9 Correct 910 ms 44784 KB Output is correct
10 Correct 781 ms 44740 KB Output is correct
11 Correct 788 ms 44780 KB Output is correct
12 Correct 784 ms 44780 KB Output is correct
13 Correct 657 ms 44780 KB Output is correct
14 Correct 648 ms 44652 KB Output is correct
15 Correct 630 ms 44656 KB Output is correct
16 Correct 481 ms 44652 KB Output is correct
17 Correct 472 ms 44780 KB Output is correct
18 Correct 480 ms 44652 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 364 KB Output is correct
2 Correct 30 ms 416 KB Output is correct
3 Correct 167 ms 492 KB Output is correct
4 Correct 169 ms 492 KB Output is correct
5 Correct 183 ms 492 KB Output is correct
6 Correct 158 ms 492 KB Output is correct
7 Correct 161 ms 492 KB Output is correct
8 Correct 167 ms 492 KB Output is correct
9 Correct 165 ms 492 KB Output is correct
10 Correct 145 ms 492 KB Output is correct
11 Correct 145 ms 484 KB Output is correct
12 Correct 145 ms 492 KB Output is correct
13 Correct 147 ms 492 KB Output is correct
14 Correct 144 ms 484 KB Output is correct
15 Correct 147 ms 492 KB Output is correct
16 Correct 146 ms 492 KB Output is correct
17 Correct 142 ms 492 KB Output is correct
18 Correct 147 ms 492 KB Output is correct
19 Correct 2248 ms 828 KB Output is correct
20 Correct 2874 ms 896 KB Output is correct
21 Correct 2814 ms 900 KB Output is correct
22 Correct 2859 ms 1004 KB Output is correct
23 Correct 2581 ms 988 KB Output is correct
24 Correct 2586 ms 876 KB Output is correct
25 Correct 2575 ms 876 KB Output is correct
26 Correct 2574 ms 852 KB Output is correct
27 Correct 2578 ms 876 KB Output is correct
28 Correct 2585 ms 876 KB Output is correct
29 Correct 79 ms 24044 KB Output is correct
30 Correct 393 ms 35256 KB Output is correct
31 Correct 687 ms 44652 KB Output is correct
32 Correct 689 ms 44656 KB Output is correct
33 Correct 838 ms 44652 KB Output is correct
34 Correct 787 ms 44652 KB Output is correct
35 Correct 913 ms 44780 KB Output is correct
36 Correct 914 ms 44652 KB Output is correct
37 Correct 910 ms 44784 KB Output is correct
38 Correct 781 ms 44740 KB Output is correct
39 Correct 788 ms 44780 KB Output is correct
40 Correct 784 ms 44780 KB Output is correct
41 Correct 657 ms 44780 KB Output is correct
42 Correct 648 ms 44652 KB Output is correct
43 Correct 630 ms 44656 KB Output is correct
44 Correct 481 ms 44652 KB Output is correct
45 Correct 472 ms 44780 KB Output is correct
46 Correct 480 ms 44652 KB Output is correct
47 Execution timed out 9067 ms 10348 KB Time limit exceeded
48 Halted 0 ms 0 KB -