Submission #335209

#	Time	Username	Problem	Language	Result	Execution time	Memory
335209		guka415	ČVENK (COI15_cvenk)	C++14	0 / 100	146 ms	10476 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) {
	int len = 1 << bit, len2 = (len >> 1);
	int lx = (x / len)*len, ly = (y / len)*len;
	if (x - lx < len2&&y - ly < len2)return 0;
	else if (x - lx >= len2)return 1;
	else return 2;
}

inline int toUpperLeft(int x, int y, int bit) {
	int len = 1 << bit, len2 = (len >> 1);
	int lx = (x / len)*len, ly = (y / len)*len;
	return dist(x, y, lx, ly);
}

inline int toZero(int x, int y, int bit) {
	int wh = whichTriangle(x, y, bit);
	if (wh == 0)return 0;
	else return toUpperLeft(x, y, bit) + 1;
}

inline int toOne(int x, int y, int bit) {
	int len = (1 << bit), len2 = len / 2;
	int wh = whichTriangle(x, y, bit), mx = (x / len)*len, my = (y / len)*len;
	if (wh == 1)return 0;
	else if (wh == 2)return toUpperLeft(x, y, bit - 1) + (1 << bit);
	else {
		int crb = bit;
		while (crb > 0) {
			wh = whichTriangle(x, y, crb);
			if(wh==2)return toUpperLeft(x, y, crb - 1) + (1 << crb);
			crb--;
		}
		return dist(mx, my, x, y);
	}
}

inline int toTwo(int x, int y, int bit) {
	int len = (1 << bit), len2 = len / 2;
	int wh = whichTriangle(x, y, bit), mx = (x / len)*len, my = (y / len)*len;
	if (wh == 2)return 0;
	else {
		int crb = bit;
		while (crb > 0) {
			wh = whichTriangle(x, y, crb);
			if (wh == 1)return toUpperLeft(x, y, crb - 1) + (1 << crb);
			crb--;
		}
		return dist(mx, my, x, y);
	}
}

const int sz = 1e5 + 5;
int n;
map<pii, ll> cnts;
ll tot = 0;

void calc(int bit) {
	if (bit == 0)return;
	map<pii, ll> cur;
	ll tots[3]{ 0,0,0 };
	bool f = 1;
	int ulx, uly;
	for (auto x : cnts) {
		if (f) {
			pii tmp = upperLeft(x.first.first, x.first.second, bit);
			ulx = tmp.first;
			uly = tmp.second;
			f = 0;
		}
		tots[0] += x.second*toZero(x.first.first, x.first.second, bit);
		tots[1] += x.second*toOne(x.first.first, x.first.second, bit);
		tots[2] += x.second*toTwo(x.first.first, x.first.second, bit);
	}
	int mni = -1;
	ll mymn = 1e16;
	foru(i, 0, 3) {
		if (tots[i] < mymn) {
			mymn = tots[i];
			mni = i;
		}
	}
	tot += mymn;
	for (auto x : cnts) {
		int wh = whichTriangle(x.first.first, x.first.second, bit);
		if (wh == mni)cur[x.first] += x.second;
		else {
			if (mni == 0) {
				pii ul = upperLeft(x.first.first, x.first.second, bit - 1);
				if (wh == 1)ul.first--;
				else ul.second--;
				cur[ul] += x.second;
			}
			else if (mni==1){
				cur[{ulx + (1 << (bit - 1)), uly}] += x.second;
			}
			else {
				cur[{ulx, uly + (1 << (bit - 1))}] += x.second;
			}
		}
	}
	cnts = cur;
	calc(bit - 1);
}

int main() {
	fast;
	cin >> n;
	int p, q;
	foru(i, 0, n) {
		cin >> p >> q;
		cnts[{p, q}]++;
	}
	calc(4);
	cout << tot << '\n';
	return 0;
}

Compilation message (stderr)

cvenk.cpp: In function 'int toUpperLeft(int, int, int)':
cvenk.cpp:39:22: warning: unused variable 'len2' [-Wunused-variable]
   39 |  int len = 1 << bit, len2 = (len >> 1);
      |                      ^~~~
cvenk.cpp: In function 'int toOne(int, int, int)':
cvenk.cpp:51:24: warning: unused variable 'len2' [-Wunused-variable]
   51 |  int len = (1 << bit), len2 = len / 2;
      |                        ^~~~
cvenk.cpp: In function 'int toTwo(int, int, int)':
cvenk.cpp:67:24: warning: unused variable 'len2' [-Wunused-variable]
   67 |  int len = (1 << bit), len2 = len / 2;
      |                        ^~~~

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