oj.uz

Submission #363203

# Submission time Handle Problem Language Result Execution time Memory
363203 2021-02-05T09:32:57 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 1772 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct
2 Correct 66 ms 364 KB Output is correct
3 Correct 479 ms 364 KB Output is correct
4 Correct 479 ms 492 KB Output is correct
5 Correct 468 ms 448 KB Output is correct
6 Correct 380 ms 492 KB Output is correct
7 Correct 408 ms 364 KB Output is correct
8 Correct 430 ms 512 KB Output is correct
9 Correct 455 ms 364 KB Output is correct
10 Correct 386 ms 364 KB Output is correct
11 Correct 386 ms 364 KB Output is correct
12 Correct 384 ms 364 KB Output is correct
13 Correct 404 ms 364 KB Output is correct
14 Correct 386 ms 448 KB Output is correct
15 Correct 389 ms 448 KB Output is correct
16 Correct 388 ms 620 KB Output is correct
17 Correct 386 ms 516 KB Output is correct
18 Correct 384 ms 492 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct
2 Correct 66 ms 364 KB Output is correct
3 Correct 479 ms 364 KB Output is correct
4 Correct 479 ms 492 KB Output is correct
5 Correct 468 ms 448 KB Output is correct
6 Correct 380 ms 492 KB Output is correct
7 Correct 408 ms 364 KB Output is correct
8 Correct 430 ms 512 KB Output is correct
9 Correct 455 ms 364 KB Output is correct
10 Correct 386 ms 364 KB Output is correct
11 Correct 386 ms 364 KB Output is correct
12 Correct 384 ms 364 KB Output is correct
13 Correct 404 ms 364 KB Output is correct
14 Correct 386 ms 448 KB Output is correct
15 Correct 389 ms 448 KB Output is correct
16 Correct 388 ms 620 KB Output is correct
17 Correct 386 ms 516 KB Output is correct
18 Correct 384 ms 492 KB Output is correct
19 Correct 7673 ms 620 KB Output is correct
20 Execution timed out 9030 ms 876 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4228 ms 836 KB Output is correct
2 Execution timed out 9092 ms 1772 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct
2 Correct 66 ms 364 KB Output is correct
3 Correct 479 ms 364 KB Output is correct
4 Correct 479 ms 492 KB Output is correct
5 Correct 468 ms 448 KB Output is correct
6 Correct 380 ms 492 KB Output is correct
7 Correct 408 ms 364 KB Output is correct
8 Correct 430 ms 512 KB Output is correct
9 Correct 455 ms 364 KB Output is correct
10 Correct 386 ms 364 KB Output is correct
11 Correct 386 ms 364 KB Output is correct
12 Correct 384 ms 364 KB Output is correct
13 Correct 404 ms 364 KB Output is correct
14 Correct 386 ms 448 KB Output is correct
15 Correct 389 ms 448 KB Output is correct
16 Correct 388 ms 620 KB Output is correct
17 Correct 386 ms 516 KB Output is correct
18 Correct 384 ms 492 KB Output is correct
19 Correct 7673 ms 620 KB Output is correct
20 Execution timed out 9030 ms 876 KB Time limit exceeded
21 Halted 0 ms 0 KB -