Submission #1200979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200979		MateiKing80	Robots (APIO13_robots)	C++20	0 / 100	1 ms	320 KiB

robots

#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <algorithm>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cassert>

#pragma GCC target("avx2,bmi,bmi,popcnt,lzcnt")

using namespace std;
using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()

using ll = long long;
using ld = long double;
//#define int ll


using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 15e4 + 5, inf = 1e9 + 5;

set<pii> av[8];
set<pii> taken[3][8];
int msks[N], xs[N], n;

pair<int, ll> curr;

void printAll(string message) {
	cout << message << '\n';
	cout << "Curr: " << curr.fr << " " << curr.sc << '\n';
	cout << "Av:\n";
	for (int i = 0; i < 8; i ++) {
		cout << i << ": ";
		for (auto j : av[i])
			cout << j.fr << " ";
		cout << '\n';
	}
	cout << "Taken\n";
	for (int k = 0; k < 3; k ++) {
		cout << "TakenK: " << k << '\n';
		for (int i = 0; i < 8; i ++) {
			cout << i << ": ";
			for (auto j : taken[k][i])
				cout << j.fr << " ";
			cout << '\n';
		}
	}
}

bool add(int x) {
	int minn = inf;
	for (int i = 0; i < 8; i ++)
		if (i & (1 << x) && !av[i].empty() && minn > (*av[i].begin()).fr)
			minn = (*av[i].begin()).fr;
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int costAdaug = inf;
		bool potSchimb = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
				costAdaug = (*av[i].begin()).fr;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
				potSchimb = 1;
		if (potSchimb)
			minn = min(minn, costAdaug);
	}
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int z = 3 - x - y;
		int costAdaug = inf;
		bool potSchimbZY = 0;
		bool potSchimbYX = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
				costAdaug = (*av[i].begin()).fr;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && i & (1 << y) && !taken[z][i].empty())
				potSchimbZY = 1;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
				potSchimbYX = 1;
		if (potSchimbYX && potSchimbZY)
			minn = min(minn, costAdaug);
	}
	
	if (minn >= inf)
		return false;
	
	curr.sc += minn;
	curr.fr ++;
	
	for (int i = 0; i < 8; i ++)
		if (i & (1 << x) && !av[i].empty() && minn == (*av[i].begin()).fr) {
			taken[x][i].insert(*av[i].begin());
			av[i].erase(av[i].begin());
			return true;
		}
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int costAdaug = inf, deUnde = -1, ad = -1;
		bool potSchimb = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
				costAdaug = (*av[i].begin()).fr, ad = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
				potSchimb = 1, deUnde = i;
		if (potSchimb && costAdaug == minn) {
			pii sus = *taken[y][deUnde].begin();
			taken[y][deUnde].erase(sus);
			taken[x][deUnde].insert(sus);
			
			sus = *av[ad].begin();
			av[ad].erase(sus);
			taken[y][ad].insert(sus);
			
			return true;
		}
	}
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int z = 3 - x - y;
		int costAdaug = inf, deUndeYX = -1, deUndeZY = -1, ad = -1;
		bool potSchimbZY = 0;
		bool potSchimbYX = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
				costAdaug = (*av[i].begin()).fr, ad = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && i & (1 << y) && !taken[z][i].empty())
				potSchimbZY = 1, deUndeZY = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
				potSchimbYX = 1, deUndeYX = i;
		if (potSchimbYX && potSchimbZY && minn == costAdaug) {
			pii sus = *taken[z][deUndeZY].begin();
			taken[z][deUndeZY].erase(sus);
			taken[y][deUndeZY].insert(sus);
			
			sus = *taken[y][deUndeYX].begin();
			taken[y][deUndeYX].erase(sus);
			taken[x][deUndeYX].insert(sus);
			
			sus = *av[ad].begin();
			av[ad].erase(sus);
			taken[z][ad].insert(sus);
			
			return true;
		}
	}
	assert(false);
}

bool rem(int x) {
	int maxx = -1;
	for (int i = 0; i < 8; i ++)
		if (i & (1 << x) && !taken[x][i].empty() && maxx < (*taken[x][i].rbegin()).fr)
			maxx = (*taken[x][i].rbegin()).fr;
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int costScot = -1;
		bool potSchimb = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && !taken[y][i].empty() && costScot < (*taken[y][i].rbegin()).fr)
				costScot = (*taken[y][i].rbegin()).fr;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[x][i].empty())
				potSchimb = 1;
		if (potSchimb)
			maxx = max(maxx, costScot);
	}
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int z = 3 - x - y;
		int costScot = -1;
		bool potSchimbYZ = 0;
		bool potSchimbXY = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && !taken[z][i].empty() && costScot < (*taken[z][i].rbegin()).fr)
				costScot = (*taken[z][i].rbegin()).fr;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << z) && !taken[y][i].empty())
				potSchimbYZ = 1;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << x) && i & (1 << y) && !taken[x][i].empty())
				potSchimbXY = 1;
		if (potSchimbXY && potSchimbYZ)
			maxx = max(maxx, costScot);
	}
	
	if (maxx == -1)
		return false;
	
	//cout << "rem: " << maxx << '\n';
	
	curr.sc -= maxx;
	curr.fr --;
	
	for (int i = 0; i < 8; i ++)
		if (i & (1 << x) && !taken[x][i].empty() && maxx == (*taken[x][i].rbegin()).fr) {
			av[i].insert(*taken[x][i].rbegin());
			taken[x][i].erase(*taken[x][i].rbegin());
			return true;
		}

	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int costScot = -1, ad = 0, deUnde = 0;
		bool potSchimb = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && !taken[y][i].empty() && costScot < (*taken[y][i].rbegin()).fr)
				costScot = (*taken[y][i].rbegin()).fr, ad = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << x) && !taken[x][i].empty())
				potSchimb = 1, deUnde = i;
		if (potSchimb && costScot == maxx) {
			pii sus = *taken[x][deUnde].rbegin();
			taken[x][deUnde].erase(sus);
			taken[y][deUnde].insert(sus);
			
			sus = *taken[y][ad].rbegin();
			av[ad].insert(sus);
			taken[y][ad].erase(sus);
			return true;
		}
	}
	for (int y = 0; y < 3; y ++) {
		if (x == y)
			continue;
		int z = 3 - x - y;
		int costScot = -1, ad = 0, deUndeXY = 0, deUndeYZ = 0;
		bool potSchimbYZ = 0;
		bool potSchimbXY = 0;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << z) && !taken[z][i].empty() && costScot < (*taken[z][i].rbegin()).fr)
				costScot = (*taken[z][i].rbegin()).fr, ad = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << y) && i & (1 << z) && !taken[y][i].empty())
				potSchimbYZ = 1, deUndeYZ = i;
		for (int i = 0; i < 8; i ++)
			if (i & (1 << x) && i & (1 << y) && !taken[x][i].empty())
				potSchimbXY = 1, deUndeXY = i;
		if (potSchimbXY && potSchimbYZ && costScot == maxx) {
			pii sus = *taken[y][deUndeYZ].rbegin();
			taken[y][deUndeYZ].erase(sus);
			taken[z][deUndeYZ].insert(sus);
			
			sus = *taken[x][deUndeXY].rbegin();
			taken[x][deUndeXY].erase(sus);
			taken[y][deUndeXY].insert(sus);
			
			sus = *taken[z][ad].rbegin();
			av[ad].insert(sus);
			taken[z][ad].erase(sus);
			return true;
		}
	}
	assert(false);
}

bool add1() {
	if (!add(0)) {
		return false;
	}
	if (!add(1)) {
		rem(0);
		return false;
	}
	if (!add(1)) {
		rem(0);
		rem(1);
		return false;
	}
	if (!add(2)) {
		rem(0);
		rem(1);
		rem(1);
		return false;
	}
	return true;
}

bool add2() {
	if (!add(0)) {
		return false;
	}
	if (!add(1)) {
		rem(0);
		return false;
	}
	if (!add(2)) {
		rem(0);
		rem(1);
		return false;
	}
	if (!add(2)) {
		rem(0);
		rem(1);
		rem(2);
		return false;
	}
	return true;
}

bool remove1() {
	int sum1 = 0, sum2 = 0;
	for (int i = 0; i < 8; i ++) {
		sum1 += taken[1][i].size();
		sum2 += taken[2][i].size();
	}
	if (sum2 == 2 * sum1)
		return false;
	if (!rem(0)) {
		return false;
	}
	if (!rem(1)) {
		add(0);
		return false;
	}
	if (!rem(1)) {
		add(0);
		add(1);
		return false;
	}
	if (!rem(2)) {
		add(0);
		add(1);
		add(1);
		return false;
	}
	return true;
}


bool remove2() {
	int sum1 = 0, sum2 = 0;
	for (int i = 0; i < 8; i ++) {
		sum1 += taken[1][i].size();
		sum2 += taken[2][i].size();
	}
	if (2 * sum2 == sum1)
		return false;
	if (!rem(0)) {
		return false;
	}
	if (!rem(1)) {
		add(0);
		return false;
	}
	if (!rem(2)) {
		add(0);
		add(1);
		return false;
	}
	if (!rem(2)) {
		add(0);
		add(1);
		add(2);
		return false;
	}
	return true;	
}

bool swap12() {
	if (!rem(1))
		return false;
	if (!add(2)) {
		add(1);
		return false;
	}
	return true;
}

bool swap21() {
	if (!rem(2))
		return false;
	if (!add(1)) {
		add(2);
		return false;
	}
	return true;
}


pair<int, ll> better(pair<int, ll> a, pair<int, ll> b) {
	if (a.fr > b.fr)
		return a;
	if (a.fr < b.fr)
		return b;
	if (a.sc < b.sc)
		return a;
	return b;
}

ll update(int pos, int val) { //ideea e ca se schimba putine chestii
	int sum1 = 0, sum2 = 0;
	for (int i = 0; i < 8; i ++) {
		sum1 += taken[1][i].size();
		sum2 += taken[2][i].size();
	}
	if (av[msks[pos]].count({xs[pos], pos})) {
		av[msks[pos]].erase({xs[pos], pos});
		xs[pos] = val;
		av[msks[pos]].insert({xs[pos], pos});
	} else {
		int loc = 0;
		if (taken[1][msks[pos]].count({xs[pos], pos}))
			loc = 1;
		if (taken[2][msks[pos]].count({xs[pos], pos}))
			loc = 2;
		if (2 * sum1 != sum2) {
			vector<int> f = {1, 2, 1};
			f[loc] --;
			taken[loc][msks[pos]].erase({xs[pos], pos});
			curr.fr --;
			curr.sc -= xs[pos];
			for (int i = 0; i < 3; i ++)
				while (f[i] --)
					rem(i);
			xs[pos] = val;
			av[msks[pos]].insert({val, pos});
			add1();
		} else {
			vector<int> f = {1, 1, 2};
			f[loc] --;
			taken[loc][msks[pos]].erase({xs[pos], pos});
			curr.fr --;
			curr.sc -= xs[pos];
			for (int i = 0; i < 3; i ++)
				while (f[i] --)
					rem(i);
			xs[pos] = val;
			av[msks[pos]].insert({val, pos});
			add2();
		}
	}
	if (remove1())
		add1();
	if (remove2())
		add2();
	pair<int, ll> ans = curr;
	if (swap12()) {
		if (better(ans, curr) == ans)
			swap21();
		ans = curr;
	}
	if (swap21()) {
		if (better(ans, curr) == ans)
			swap12();
		ans = curr;
	}
	return ans.sc;
}

pair<int, ll> solve() {
	for (int i = 0; i < n; i ++)
		av[msks[i]].insert({xs[i], i});
	pair<int, ll> ans = {0, 0};
	curr = {0, 0};
	while (1) {
		ans = better(ans, curr);
		if (!add1())
			break;
	}
	while (1) {
		ans = better(ans, curr);
		if (add2())
			continue;
		if (swap12())
			continue;
		break;
	}
	for (int i = 0; i < 8; i ++) {
		av[i].clear();
		for (int j = 0; j < 3; j ++)
			taken[j][i].clear();
	}
	
	for (int i = 0; i < n; i ++)
		av[msks[i]].insert({xs[i], i});
	curr = {0, 0};
	while (1) {
		if (ans == curr)
			break;
		if (!add1())
			break;
	}
	while (1) {
		if (ans == curr)
			break;
		if (add2())
			continue;
		if (swap12())
			continue;
		break;
	}
	return {ans.fr / 4, ans.sc};
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i ++) {
		int msk, x;
		cin >> msk >> x;
		int sus = 0;
		if (msk >= 100) {
			msk -= 100;
			sus ++;
		}
		if (msk >= 10) {
			msk -= 10;
			sus += 2;
		}
		if (msk) {
			msk --;
			sus += 4;
		}
		msks[i] = sus;
		xs[i] = x;
	}
	pair<int, ll> ans = solve();
	cout << ans.fr << " " << ans.sc << '\n';
	int q;
	cin >> q;
	
	while (q --) {
		int x, y;
		cin >> x >> y;
		ll sus = update(x - 1, y);
		cout << sus << '\n';
	}
}

/*
fac o chestie de genu
fac for prin numarul de echipe <- cred ca e usor calculabil
apoi fixez numarul de echipe cu 2 matematicieni
daca calculez corect numarul ce se intampla pentru asta, 
ca sa pot schimba un matematician la informatician am mai multe variante:


iau cel mai ieftin informatician de pe bara {
	dau afara un matematician SAU
	transform un matematician in ciucuiala, ciucuiala e dat afara
} SAU {
	transform un matematician in informatician
	transform un ciucuiala in informatician {
		iau un ciucuiala de pe bara si dau afara un matematician
		transform un matematician in ciucuiala
	}
} -> merge pentru Q = 0, 53 pct, mai mult ca suficient

acuma numarul de echipe cum il fac :/
fac greeeeeeeeedy 
imi fac prima data o echipa
apoi inca una
sinca una
...
ideea e ca eu o sa am nevoie de update-uri de tipul:
scoate X optim
baga X optim

scoate e usor, scoti al mai ieftin -> fals

la baga X : {
	bagi cel mai ieftin X de pe bara
	bagi Y, schimbi Y in X
	bagi Z, schimbi Z in Y, schimbi Y in X
}

la scoate X : {
	scoti cel mai scump X
	scoti Y, schimbi X in Y
	scoti Z, schimbi X in Y, schimbi Y in Z
}

-> daca asta e corect, nu cred ca e atat de deep

am nevoie acum sa fac subtask-ul 2
nr de echipe
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40