Submission #393645

#	Time	Username	Problem	Language	Result	Execution time	Memory
393645		JimmyZJX	Ancient Books (IOI17_books)	C++14	22 / 100	2081 ms	881904 KiB

books

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;

#define forR(i, n) for (int i = 0; i < (n); i++)

const int INF = 1 << 25;

int dist(int x1, int x2, int y1, int y2) {
	int d1 = x1 - y2, d2 = x2 - y1;
	if (d1 > 0 == d2 > 0)
		return min(abs(d1), abs(d2));
	return 0;
}

LL minimum_walk(Vi p, int s) {

	int n = p.size();

	LL ans = 0;
	Vi g(n);
	Vii gps(1); // dummy
	int gn = 0; // [1, gn]
	Vi gpMin(1, s), gpMax(1, s);

	forR(i, n) {
		if (p[i] == i) continue;

		gn++;
		Vi gp;
		int mi = INF, ma = -1;

		int h = p[i];
		int pos = i;
		g[i] = gn; gp.push_back(i); mi = min(mi, i); ma = max(ma, i);
		while (h != i) {
			ans += abs(h - pos);
			pos = h;
			g[h] = gn; gp.push_back(h); mi = min(mi, h); ma = max(ma, h);
			swap(h, p[h]);
		}
		ans += abs(pos - i);
		p[i] = i;
		gps.push_back(gp);
		gpMin.push_back(mi); gpMax.push_back(ma);
	}


	Vii nbs(n);
	Vii nbDs(n);

	for (int i = 0; i <= gn; i++) {
		for (int j = 0; j <= gn; j++) {
			nbs[i].push_back(j);
			nbDs[i].push_back(dist(gpMin[i], gpMax[i], gpMin[j], gpMax[j]));
		}
	}

	//for (int i = 1; i <= gn; i++) {
	//	auto& gp = gps[i];
	//	map<int, int> distToGp;
	//	distToGp[0] = INF;
	//	for (int j : gp) {
	//		distToGp[0] = min(distToGp[0], abs(j - s));
	//		// left
	//		for (int k = j - 1; k >= 0; k--) {
	//			if (g[k] > 0) {
	//				if (g[k] != g[i]) {
	//					// other group
	//					int d = abs(j - k);
	//					if (distToGp.count(g[k]) > 0) {
	//						distToGp[g[k]] = min(distToGp[g[k]], d);
	//					} else {
	//						distToGp[g[k]] = d;
	//					}
	//				}
	//				break;
	//			}
	//		}
	//		// right
	//		for (int k = j + 1; k < n; k++) {
	//			if (g[k] > 0) {
	//				if (g[k] != g[i]) {
	//					// other group
	//					int d = abs(j - k);
	//					if (distToGp.count(g[k]) > 0) {
	//						distToGp[g[k]] = min(distToGp[g[k]], d);
	//					} else {
	//						distToGp[g[k]] = d;
	//					}
	//				}
	//				break;
	//			}
	//		}
	//	}

	//	for (auto p : distToGp) {
	//		nbs[i].push_back(p.first);
	//		nbDs[i].push_back(p.second);
	//	}
	//	nbs[0].push_back(i);
	//	nbDs[0].push_back(distToGp[0]);
	//}

	// MST
	LL mst = 0;
	Vb vis(gn + 1);
	set<pair<int, int>> minQ; // {dist, gp}
	minQ.insert({ 0, 0 });
	while (!minQ.empty()) {
		auto t = *minQ.begin(); minQ.erase(t);
		int gp = t.second;
		if (vis[gp]) continue;
		mst += t.first;
		vis[gp] = true;
		forR(i, nbs[gp].size()) {
			minQ.insert({ nbDs[gp][i], nbs[gp][i] });
		}
	}

	return ans + mst * 2;

}

#ifdef TEST_LOCAL

int main() {
	auto r = minimum_walk(Vi{ 3, 2, 1, 0 }, 0);

	return 0;
}
#endif

Compilation message (stderr)

books.cpp: In function 'int dist(int, int, int, int)':
books.cpp:34:9: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   34 |  if (d1 > 0 == d2 > 0)
      |      ~~~^~~
books.cpp: In function 'LL minimum_walk(Vi, int)':
books.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
books.cpp:139:3: note: in expansion of macro 'forR'
  139 |   forR(i, nbs[gp].size()) {
      |   ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30