Submission #335215

#	Time	Username	Problem	Language	Result	Execution time	Memory
335215		guka415	ČVENK (COI15_cvenk)	C++14	17 / 100	202 ms	13036 KiB

cvenk

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll; //OVERFLOW


inline int dist(int x, int y, int lx, int ly) {
	return abs(x - lx) + abs(y - ly);
}

inline pii upperLeft(int x, int y, int bit) {
	int len = (1 << bit);
	return { (x / len)*len,(y / len)*len };
}

inline int whichTriangle(int x, int y, int bit) {
	pii ul = upperLeft(x, y, bit);
	int len2 = (1 << (bit - 1));
	if (x - ul.first < len2&&y - ul.second < len2)return 0;
	else if (x - ul.first >= len2)return 1;
	else return 2;
}


inline int tz(int x, int y, int bit) {
	if (whichTriangle(x, y, bit) == 0)return 0;
	pii ttt = upperLeft(x, y, bit-1);
	return dist(ttt.first, ttt.second, x, y) + 1;
}
inline int to(int x, int y, int bit) {
	pii ttt = upperLeft(x, y, bit);
	int tx = (1 << (bit - 1)), ty = 0;
	switch (whichTriangle(x, y, bit)) {
	case 1:
		return 0;
	case 2:
		return dist(ttt.first, ttt.second, x, y) + (1 << (bit - 1));
	case 0:
		int mx = x - ttt.first, my = y - ttt.second, crb = bit;
		ll bst = 1e18;
		while (crb > 0) {
			pii tmp = upperLeft(mx, my, crb);
			if (tmp.first&&tmp.second)return bst;
			bst = min(bst, (ll)dist(tmp.first, tmp.second, mx, my) + dist(tmp.first, tmp.second, tx, ty));
			crb--;
		}
		return bst;
	}
	return -1;
}
inline int tt(int x, int y, int bit) {
	pii ttt = upperLeft(x, y, bit);
	int ty = (1 << (bit - 1)), tx = 0;
	switch (whichTriangle(x, y, bit)) {
	case 2:
		return 0;
	case 1:
		return dist(ttt.first, ttt.second, x, y) + (1 << (bit - 1));
	case 0:
		int mx = x - ttt.first, my = y - ttt.second, crb = bit;
		ll bst = 1e18;
		while (crb > 0) {
			pii tmp = upperLeft(mx, my, crb);
			if (tmp.first&&tmp.second)return bst;
			bst = min(bst, (ll)dist(tmp.first, tmp.second, mx, my) + dist(tmp.first, tmp.second, tx, ty));
			crb--;
		}
		return bst;
	}
	return -1;
}


int main() {
	fast;
	int n;
	map<pii, ll> mem;
	cin >> n;
	foru(i, 0, n) {
		int ax, bx;
		cin >> ax >> bx;
		mem[{ax, bx}]++;
	}
	int cbt = 30;
	ll tot = 0;
	while (cbt > 0) {
		ll crtot[3]{ 0,0,0 };
		map<pii, ll> cnts;
		bool f = 1;
		pii ul;
		for (auto x : mem) {
			if (f) {
				ul = upperLeft(x.first.first, x.first.second, cbt);
				f = 0;
			}
			crtot[0] += x.second*tz(x.first.first, x.first.second, cbt);
			crtot[1] += x.second*to(x.first.first, x.first.second, cbt);
			crtot[2] += x.second*tt(x.first.first, x.first.second, cbt);
		}
		int mni = -1;
		ll mymn = 1e18;
		foru(i, 0, 3) {
			if (crtot[i] < mymn) {
				mymn = crtot[i];
				mni = i;
			}
		}
		pll out1 = { ul.first + (1 << (cbt - 1)),ul.second };
		pll out2 = { ul.first,ul.second + (1 << (cbt - 1)) };
		switch (mni) {
		case 0:
			for (auto x : mem) {
				switch (whichTriangle(x.first.first, x.first.second, cbt)) {
				case 0:
					cnts[x.first] += x.second;
					break;
				case 1:
					cnts[{out1.first - 1, out1.second}] += x.second;
					break;
				case 2:
					cnts[{out2.first, out2.second - 1}] += x.second;
					break;
				}
			}
			break;
		case 1:
			for (auto x : mem) {
				if (whichTriangle(x.first.first, x.first.second, cbt) != 1) cnts[out1] += x.second;
				else cnts[x.first] += x.second;
			}
			break;
		case 2:
			for (auto x : mem) {
				if (whichTriangle(x.first.first, x.first.second, cbt) != 2) cnts[out2] += x.second;
				else cnts[x.first] += x.second;
			}
			break;
		}
		mem = cnts;
		tot += mymn;
		cbt--;
	}
	cout << tot << '\n';
	return 0;
}

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