Submission #364742

#	Time	Username	Problem	Language	Result	Execution time	Memory
364742		r57shell	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	761 ms	524292 KiB

bubblesort2

#include "bubblesort2.h"
#include <cstdio>
#include <string>
#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;
}

void merge(vector<int> &res, const vector<int> &a, const vector<int> &b)
{
	int i, j, k;
	res.resize(a.size()+b.size());
	k = 0;
	for (i = 0, j = 0; i < a.size() && j < b.size(); )
	{
		if (a[i] <= b[j])
			res[k++] = a[i++];
		else
			res[k++] = b[j++];
	}
	for (; i < a.size(); ++i, ++k)
		res[k] = a[i];
	for (; j < b.size(); ++j, ++k)
		res[k] = b[j];
}

static int smart2(const vector<int> &A, vector<vector<int>> &T)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = 0; i < n; ++i)
		T[i+n].assign(1, A[i]);
	for (int i = n - 1; i > 0; --i)
		merge(T[i], T[i*2], T[i*2+1]);
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			int l = 0 + n;
			int r = i + n;
			while (l <= r)
			{
				if (l&1)
					c += T[l].size() - (lower_bound(T[l].begin(), T[l].end(), p + 1) - T[l].begin());
				if (!(r&1))
					c += T[r].size() - (lower_bound(T[r].begin(), T[r].end(), p + 1) - T[r].begin());
				l = (l+1)/2;
				r = (r-1)/2;
			}
			res = max(res, c);
		}
	}
	return res;
}

static int smart3(const vector<int> &A, vector<vector<int>> &T)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = 0; i < n; ++i)
		T[i].clear();
	/*for (int i = 0; i < n; ++i)
		printf("%d ", A[i]);
	printf("\n");*/
	vector<int> v, v1;
	for (int i = 0; i < n; ++i)
	{
		//for (int x = i; x < n; x = (x|(x+1)))
		//	T[x].push_back(A[i]);
			//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
		v.assign(1, A[i]);
		v1.clear();
		int y = (i&(i+1))-1;
		for (int x = i - 1; x > y; x = (x&(x+1))-1)
		{
			merge(v1, v, T[x]);
			swap(v1, v);
		}
		T[i] = v;
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
				c += T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin());
			res = max(res, c);
		}
	}
	return res;
}

struct node
{
	node *left;
	node *right;
	int h;
	int v;
	int v1;
	int sz;
	int pv;
	int mv;
};

void traverse(node *a)
{
	if (!a)
		return;
	traverse(a->left);
	printf("%d ", a->v);
	fflush(stdout);
	traverse(a->right);
}

string tostr(node *a)
{
	if (!a)
		return string();
	string r = tostr(a->left);
	char tmp[20];
	sprintf(tmp," (%d, %d, %d, %d)", a->v, a->v1, a->mv, a->pv);
	r += tmp;
	return r + tostr(a->right);
}

vector<int> grab(node *a, int pv)
{
	if (!a)
		return vector<int>();
	vector<int> r = grab(a->left, pv+a->pv);
	r.push_back(pv+a->v1);
	vector<int> rb = grab(a->right, pv+a->pv);
	for (int i = 0; i < rb.size(); ++i)
		r.push_back(rb[i]);
	return r;
}

node * merge(node *a, node *b)
{
	if (!a)
		return b;
	if (!b)
		return a;
	node *r = new node();
	//vector<int> qwe = grab(a,0);
	//vector<int> qwe1 = grab(b,0);
	//for (int i = 0; i < qwe1.size(); ++i)
	//	qwe.push_back(qwe1[i]);
	if (a->h < b->h)
	{
		*r = *a;
		node *a_right = a->right;
		if (r->pv)
		{
			int delta = r->pv;
			if (a->left)
			{
				node *nl = new node();
				*nl = *a->left;
				nl->pv += delta;
				nl->mv += delta;
				nl->v1 += delta;
				r->left = nl;
			}
			if (a->right)
			{
				a_right = new node();
				*a_right = *a->right;
				a_right->pv += delta;
				a_right->mv += delta;
				a_right->v1 += delta;
			}
			r->pv = 0;
		}
		r->right = merge(a_right, b);
	}
	else
	{
		*r = *b;
		node *b_left = b->left;
		if (r->pv)
		{
			int delta = r->pv;
			if (b->right)
			{
				node *nr = new node();
				*nr = *b->right;
				nr->pv += delta;
				nr->mv += delta;
				nr->v1 += delta;
				r->right = nr;
			}
			if (b->left)
			{
				b_left = new node();
				*b_left = *b->left;
				b_left->pv += delta;
				b_left->mv += delta;
				b_left->v1 += delta;
			}
			r->pv = 0;
		}
		r->left = merge(a, b_left);
	}
	r->sz = 1;
	r->mv = r->v1;
	if (r->left)
	{
		r->sz += r->left->sz;
		r->mv = max(r->mv, r->left->mv);
	}
	if (r->right)
	{
		r->sz += r->right->sz;
		r->mv = max(r->mv, r->right->mv);
	}
	/*vector<int> qwe2 = grab(r,0);
	int mmm = int(-1e9);
	for (int i = 0; i < qwe.size(); ++i)
		mmm = max(mmm, qwe[i]);
	if (qwe != qwe2 || r->mv != mmm)
	{
		printf("======= wrong ==== %d %d\n", r->mv, mmm);
		for (int i = 0; i < qwe.size(); ++i)
			printf("%d ", qwe[i]);
		printf("\n");
		for (int i = 0; i < qwe2.size(); ++i)
			printf("%d ", qwe2[i]);
		printf("\n [%s] [%s]\n", tostr(a).c_str(), tostr(b).c_str());
	}*/
	return r;
}

pair<node*,node*> split(node *a, int x)
{
	if (!a)
		return pair<node*,node*>((node*)0, (node*)0);
	pair<node*,node*> tmp;
	//vector<int> qwe = grab(a,0);
	//pair<node*,node*> ans;
	if (x <= a->v)
	{
		node * a_left = a->left;
		if (a->pv && a_left)
		{
			int pv = a->pv;
			a_left = new node();
			*a_left = *a->left;
			a_left->pv += pv;
			a_left->mv += pv;
			a_left->v1 += pv;
		}
		tmp = split(a_left,x);
		node * z = new node();
		*z = *a;
		z->left = NULL;
		if (a->left)
			z->sz -= a->left->sz;
		z->mv = z->v1;
		if (z->right)
			z->mv = max(z->mv, z->right->mv + z->pv);
		return pair<node*,node*>(tmp.first, merge(tmp.second,z));
	}
	else
	{
		node *a_right = a->right;
		if (a->pv && a_right)
		{
			int pv = a->pv;
			a_right = new node();
			*a_right = *a->right;
			a_right->pv += pv;
			a_right->mv += pv;
			a_right->v1 += pv;
		}
		tmp = split(a_right,x);
		node * z = new node();
		*z = *a;
		z->right = NULL;
		if (a->right)
			z->sz -= a->right->sz;
		z->mv = z->v1;
		if (z->left)
			z->mv = max(z->mv, z->left->mv + z->pv);
		return pair<node*,node*>(merge(z, tmp.first), tmp.second);
	}
	/*vector<int> qwe1 = grab(ans.first,0);
	vector<int> qwe2 = grab(ans.second,0);
	for (int i = 0; i < qwe2.size(); ++i)
		qwe1.push_back(qwe2[i]);
	if (qwe1 != qwe)
	{
		printf("======= wrong split ====\n");
		for (int i = 0; i < qwe.size(); ++i)
			printf("%d ", qwe[i]);
		printf("\n");
		for (int i = 0; i < qwe1.size(); ++i)
			printf("%d ", qwe1[i]);
		printf("\n [%s] %d\n", tostr(a).c_str(), x);
	}
	return ans;*/
}

node * removefirst(node *a)
{
	//string z = tostr(a);
	node *r = NULL;
	//string ll = tostr(a->left);
	//string rr = tostr(a->right);
	if (a->left)
	{
		node *q = new node();
		*q = *a;
		q->left = NULL;
		q->sz -= a->left->sz;
		r = merge(removefirst(a->left), q);
	}
	else
		r = a->right;
	//printf("remove first (%s) (%s) (%s) = %s\n", z.c_str(), ll.c_str(), rr.c_str(), tostr(r).c_str());
	return r;
}

int getsz(node *a, int x)
{
	if (!a)
		return 0;
	if (a->v < x)
		return (a->left ? a->left->sz : 0) + 1 + getsz(a->right, x);
	return getsz(a->left, x);
}

static int smart4(const vector<int> &A)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	vector<node*> D(2*n);
	{
		vector<vector<int>> T(2*n);
		/*for (int i = 0; i < n; ++i)
			printf("%d ", A[i]);
		printf("\n");*/
		vector<int> v, v1;
		for (int i = 0; i < n; ++i)
		{
			//for (int x = i; x < n; x = (x|(x+1)))
			//	T[x].push_back(A[i]);
				//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
			v.assign(1, A[i]);
			v1.clear();
			int y = (i&(i+1))-1;
			for (int x = i - 1; x > y; x = (x&(x+1))-1)
			{
				merge(v1, v, T[x]);
				swap(v1, v);
			}
			T[i] = v;
			D[i] = NULL;
			for (int j = 0; j < v.size(); ++j)
			{
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = v[j];
				nd->left = NULL;
				nd->right = NULL;
				nd->sz = 1;
				D[i] = merge(D[i], nd);
			}
		}
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
			{
				//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
				c += D[x]->sz - getsz(D[x], p+1);
			}
			res = max(res, c);
		}
	}
	return res;
}

static int smart5(const vector<int> &A, vector<node*> &D)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	if (D.size() == 0)
	{
		D.resize(2*n);
		vector<vector<int>> T(2*n);
		/*for (int i = 0; i < n; ++i)
			printf("%d ", A[i]);
		printf("\n");*/
		vector<int> v, v1;
		for (int i = 0; i < n; ++i)
		{
			//for (int x = i; x < n; x = (x|(x+1)))
			//	T[x].push_back(A[i]);
				//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
			v.assign(1, A[i]);
			v1.clear();
			int y = (i&(i+1))-1;
			for (int x = i - 1; x > y; x = (x&(x+1))-1)
			{
				merge(v1, v, T[x]);
				swap(v1, v);
			}
			T[i] = v;
			D[i] = NULL;
			for (int j = 0; j < v.size(); ++j)
			{
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = v[j];
				nd->left = NULL;
				nd->right = NULL;
				nd->sz = 1;
				D[i] = merge(D[i], nd);
			}
		}
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
			{
				//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
				c += D[x]->sz - getsz(D[x], p+1);
			}
			res = max(res, c);
		}
	}
	return res;
}

vector<int> countScans1(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	vector<node*> D;
	//vector<vector<int>> T(N);
	for (int j = 0; j < Q; ++j)
	{
		//printf("j %d\n", j);
		if (j != 0)
		{
			//for (int x = 0; x < N; ++x)
			//	printf("%d ", A[x]);
			//printf("\n");
			//printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);
			for (int x = X[j]; x < N; x = (x|(x+1)))
			{
				//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
				//traverse(D[x]);
				//printf("\n");
				pair<node*,node*> tmp = split(D[x], A[X[j]]);
				//traverse(tmp.first);
				//printf(", ");
				//traverse(tmp.second);
				//printf("\n");
				tmp.second = removefirst(tmp.second);
				//traverse(tmp.second);
				//printf("\n");
				node * q = merge(tmp.first, tmp.second);
				//printf("=");
				//traverse(q);
				//printf("\n");
				tmp = split(q,V[j]);
				node * nn = new node();
				nn->h = rand()*32000+rand();
				nn->left = 0;
				nn->right = 0;
				nn->sz = 1;
				nn->v = V[j];
				//printf("D[%d] = ", x);
				D[x] = merge(merge(tmp.first, nn), tmp.second);
				//traverse(D[x]);
				//printf("\n");
			}
		}
		A[X[j]] = V[j];
		answer[j] = smart5(A, D);
	}
	return answer;
}

node* getleft(node *a)
{
	if (a->left)
		return getleft(a->left);
	return a;
}

vector<node*> DS;
vector<vector<pair<int,int>>> DP;

void apply_push(int x)
{
	vector<pair<int,int>> &v = DP[x];
	for (int i = 0; i < v.size(); ++i)
	{
		int a = v[i].first;
		int delta = v[i].second;
		if (x*2+1 < DP.size())
		{
			DP[x*2].push_back(v[i]);
			DP[x*2+1].push_back(v[i]);
		}
		//printf("before split DS[%d] \"%s\" (%d, %d)\n", x, tostr(DS[x]).c_str(), a, delta);
		pair<node*,node*> q = split(DS[x], a);
		//printf("after split \"%s\" (%d, %d) \"%s\"\n", tostr(q.first).c_str(), a, delta, tostr(q.second).c_str());
		if (q.first)
		{
			node *nn = new node();
			*nn = *(q.first);
			nn->pv += delta;
			nn->mv += delta;
			nn->v1 += delta;
			DS[x] = merge(nn, q.second);
		}
		else
			DS[x] = q.second;
		//printf("result \"%s\"\n", tostr(DS[x]).c_str());
	}
	v.clear();
}

void merge_seq(int x)
{
	apply_push(x*2+1);
	node *right = DS[x*2+1];
	int cut;
	if (right)
		cut = getleft(right)->v;
	else
		cut = int(2e9);
	apply_push(x*2);
	node *left = DS[x*2];
	pair<node*, node*> tmp = split(left, cut);
	DS[x] = merge(tmp.first, right);
}

void add_ab(int x, int a, int v)
{
	DP[x].push_back(pair<int,int>(a,v));
}

void dsupdate(int x, int pos, int was, int now, int inv, int L, int R)
{
	//printf("%d %d %d\n", x, L, R);
	if (R < pos)
		return;
	if (pos < L)
	{
		add_ab(x, was, -1);
		add_ab(x, now, 1);
		return;
	}
	if (L == R)
	{
		DP[x].clear();
		node * nn = new node();
		*nn = *(DS[x]);
		nn->v = now;
		nn->v1 = inv;
		nn->pv = 0;
		nn->mv = inv;
		DS[x] = nn;
		return;
	}
	int z = DP[x].size();
	for (int i = 0; i < z; ++i)
	{
		DP[2*x].push_back(DP[x][i]);
		DP[2*x+1].push_back(DP[x][i]);
	}
	DP[x].clear();
	int m = (L + R)/2;
	dsupdate(2 * x, pos, was, now, inv, L, m);
	dsupdate(2 * x + 1, pos, was, now, inv, m + 1, R);
	merge_seq(x);
	//printf("DS[%d]=%s\n",x,tostr(DS[x]).c_str());
}


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<node*> D(N);
	int TSTART = 2;
	while (TSTART / 2 < N)
		TSTART *= 2;
	DS.resize(2*TSTART);
	DP.resize(2*TSTART);
	for (int j = 0; j < Q; ++j)
	{
		//printf("j %d\n", j);
		if (j == 0)
		{
			vector<vector<int>> T(2*N);
			A[X[j]] = V[j];
			/*for (int i = 0; i < N; ++i)
				printf("%d ", A[i]);
			printf("\n");*/
			vector<int> v, v1;
			for (int i = 0; i < N; ++i)
			{
				//for (int x = i; x < n; x = (x|(x+1)))
				//	T[x].push_back(A[i]);
					//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
				v.assign(1, A[i]);
				v1.clear();
				int y = (i&(i+1))-1;
				for (int x = i - 1; x > y; x = (x&(x+1))-1)
				{
					merge(v1, v, T[x]);
					swap(v1, v);
				}
				T[i] = v;
				D[i] = NULL;
				for (int j = 0; j < v.size(); ++j)
				{
					node *nd = new node();
					nd->h = rand()*32000+rand();
					nd->v = v[j];
					nd->left = NULL;
					nd->right = NULL;
					nd->sz = 1;
					D[i] = merge(D[i], nd);
				}
			}
			for (int i = 0; i < N; ++i)
			{
				int p = A[i];
				int c = 0;
				for (int x = i; x >= 0; x = (x&(x+1))-1)
				{
					//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
					c += D[x]->sz - getsz(D[x], p+1);
				}
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = A[i];
				nd->v1 = c;
				nd->pv = 0;
				nd->mv = c;
				nd->sz = 1;
				DS[i+TSTART] = nd;
			}
			for (int i = TSTART-1; i > 0; --i)
			{
				//printf("merge_seq(%d) =", i);
				merge_seq(i);
				//printf("%s\n", tostr(DS[i]).c_str());
			}
		}
		else
		{
			/*for (int x = 0; x < N; ++x)
				printf("%d ", A[x]);
			printf("\n");
			printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);*/
			int awas = A[X[j]];
			for (int x = X[j]; x < N; x = (x|(x+1)))
			{
				//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
				//traverse(D[x]);
				//printf("\n");
				pair<node*,node*> tmp = split(D[x], awas);
				//traverse(tmp.first);
				//printf(", ");
				//traverse(tmp.second);
				//printf("\n");
				tmp.second = removefirst(tmp.second);
				//traverse(tmp.second);
				//printf("\n");
				node * q = merge(tmp.first, tmp.second);
				//printf("=");
				//traverse(q);
				//printf("\n");
				tmp = split(q,V[j]);
				node * nn = new node();
				nn->h = rand()*32000+rand();
				nn->left = 0;
				nn->right = 0;
				nn->sz = 1;
				nn->v = V[j];
				//printf("D[%d] = ", x);
				D[x] = merge(merge(tmp.first, nn), tmp.second);
				//traverse(D[x]);
				//printf("\n");
			}
			{
				int p = V[j];
				int c = 0;
				for (int x = X[j]; x >= 0; x = (x&(x+1))-1)
				{
					//printf("yo %d %s\n", x, tostr(D[x]).c_str());
					//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
					c += D[x]->sz - getsz(D[x], p+1);
				}
				//printf("dsupdate inv = %d\n", c);
				dsupdate(1, X[j], awas, V[j], c, 0, TSTART-1);
			}
			/*{
				int x = TSTART + X[j];
				node * nn = new node();
				*nn = *(DS[x]);
				nn->v = V[j];
				nn->mv = v;
				while( x > 1 )
				{
					x /= 2;
					merge_seq(x);
				}
			}*/
		}
		A[X[j]] = V[j];
		apply_push(1);
		//printf("ans=%d\n", DS[1]->mv);
		answer[j] = DS[1]->mv;//smart5(A, D);
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (; x < f.size(); x |= (x+1))
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void merge(std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
bubblesort2.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                                     ~~^~~~~~~~~~
bubblesort2.cpp:107:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (; i < a.size(); ++i, ++k)
      |         ~~^~~~~~~~~~
bubblesort2.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for (; j < b.size(); ++j, ++k)
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> grab(node*, int)':
bubblesort2.cpp:225:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |  for (int i = 0; i < rb.size(); ++i)
      |                  ~~^~~~~~~~~~~
bubblesort2.cpp: In function 'int smart4(const std::vector<int>&)':
bubblesort2.cpp:452:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  452 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'int smart5(const std::vector<int>&, std::vector<node*>&)':
bubblesort2.cpp:509:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  509 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void apply_push(int)':
bubblesort2.cpp:603:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  603 |  for (int i = 0; i < v.size(); ++i)
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:607:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  607 |   if (x*2+1 < DP.size())
      |       ~~~~~~^~~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:726:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  726 |     for (int j = 0; j < v.size(); ++j)
      |                     ~~^~~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:425:12: warning: 'int smart4(const std::vector<int>&)' defined but not used [-Wunused-function]
  425 | static int smart4(const vector<int> &A)
      |            ^~~~~~
bubblesort2.cpp:145:12: warning: 'int smart3(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
  145 | static int smart3(const vector<int> &A, vector<vector<int>> &T)
      |            ^~~~~~
bubblesort2.cpp:113:12: warning: 'int smart2(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
  113 | static int smart2(const vector<int> &A, vector<vector<int>> &T)
      |            ^~~~~~
bubblesort2.cpp:75:12: warning: 'int smart1(const std::vector<int>&)' defined but not used [-Wunused-function]
   75 | static int smart1(const vector<int> &A)
      |            ^~~~~~
bubblesort2.cpp:61:12: warning: 'int smart(const std::vector<int>&, std::vector<int>&, const std::vector<int>&)' defined but not used [-Wunused-function]
   61 | static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
      |            ^~~~~
bubblesort2.cpp:46:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
   46 | static int stupid1(vector<int> A)
      |            ^~~~~~~
bubblesort2.cpp:9:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
    9 | static int stupid(vector<int> A)
      |            ^~~~~~

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