Submission #334352

#	Time	Username	Problem	Language	Result	Execution time	Memory
334352		CodeTiger927	ČVENK (COI15_cvenk)	C++14	0 / 100	3070 ms	3052 KiB

cvenk

using namespace std;

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

#define MAXN 100005

int N,qx[MAXN],qy[MAXN];
map<pair<int,int>,pair<pair<int,int>,int>> edges;
set<pair<int,int>> s;

pair<int,int> LCA(pair<int,int> p1,pair<int,int> p2) {
	vector<pair<int,int>> v1,v2;
	v1.push_back(p1);
	while(p1.first != 0 || p1.second != 0) {
		for(int i = 0;i <= 31;++i) {
			int cur = 1 << i;
			if(p1.first % cur != 0) {
				p1.first -= cur >> 1;
				v1.push_back(p1);
			}else if(p1.second % cur != 0) {
				p1.second -= cur >> 1;
				v1.push_back(p1);
			}
		}
	}
	v2.push_back(p2);
	while(p2.first != 0 || p2.second != 0) {
		for(int i = 0;i <= 31;++i) {
			int cur = 1 << i;
			if(p2.first % cur != 0) {
				p2.first -= cur >> 1;
				v2.push_back(p2);
			}else if(p2.second % cur != 0) {
				p2.second -= cur >> 1;
				v2.push_back(p2);
			}
		}
	}
	// for(int i = 0;i < v1.size();++i) {
	// 	cout << v1[i].first << "  " << v1[i].second << endl;
	// }
	// cout << endl;
	// for(int i = 0;i < v2.size();++i) {
	// 	cout << v2[i].first << "  " << v2[i].second << endl;
	// }
	int where = -1;
	for(int i = min(v1.size() - 1,v2.size() - 1);i >= 0;--i) {
		// cout << v1[i].first << " " << v1[i].second << "   " << v2[i].first << " " << v2[i].second << endl; 
		if(v1[v1.size() - 1 - i] == v2[v2.size() - 1 - i]) {
			where = i;
			break;
		}
	}
	if(where == -1) {
		return {0,0};
	}
	if(where != min(v1.size() - 1,v2.size() - 1)) where++;
	return {min(v1[v1.size() - 1 - where].first,v2[v2.size() - 1 - where].first),min(v1[v1.size() - 1 - where].second,v2[v2.size() - 1 - where].second)};
}

int main() {
	cin >> N;
	for(int i = 0;i < N;++i) {
		cin >> qx[i] >> qy[i];
	}
	for(int i = 0;i < N;++i) {
		for(int j = i;j < N;++j) {
			s.insert(LCA({qx[i],qy[i]},{qx[j],qy[j]}));
		}
	}
	long long ans = 1e15;
	for(auto itr = s.begin();itr != s.end();++itr) {
		long long curN = 0;
		for(int i = 0;i < N;++i) {
			pair<int,int> cur = LCA(*itr,{qx[i],qy[i]});
			curN += abs(cur.first - qx[i]) + abs(cur.second - qy[i]) + abs(cur.first - itr -> first) + abs(cur.second - itr -> second);
		}
		ans = min(ans,curN);
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

cvenk.cpp: In function 'std::pair<int, int> LCA(std::pair<int, int>, std::pair<int, int>)':
cvenk.cpp:60:11: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   60 |  if(where != min(v1.size() - 1,v2.size() - 1)) where++;
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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