Submission #393645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393645	2021-04-24T07:37:22 Z	JimmyZJX	Ancient Books (IOI17_books)	C++14	22 / 100	2000 ms	881904 KB

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

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	208 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	296 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	208 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	296 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	296 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	14 ms	2324 KB	Output is correct
23	Correct	15 ms	2428 KB	Output is correct
24	Correct	15 ms	2480 KB	Output is correct
25	Correct	17 ms	2712 KB	Output is correct
26	Correct	5 ms	936 KB	Output is correct
27	Correct	4 ms	588 KB	Output is correct
28	Correct	1 ms	460 KB	Output is correct
29	Correct	17 ms	2660 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	208 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	296 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	296 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	14 ms	2324 KB	Output is correct
23	Correct	15 ms	2428 KB	Output is correct
24	Correct	15 ms	2480 KB	Output is correct
25	Correct	17 ms	2712 KB	Output is correct
26	Correct	5 ms	936 KB	Output is correct
27	Correct	4 ms	588 KB	Output is correct
28	Correct	1 ms	460 KB	Output is correct
29	Correct	17 ms	2660 KB	Output is correct
30	Correct	248 ms	70648 KB	Output is correct
31	Correct	251 ms	70496 KB	Output is correct
32	Correct	166 ms	65620 KB	Output is correct
33	Execution timed out	2081 ms	881904 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	2124 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	208 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	296 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	296 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	14 ms	2324 KB	Output is correct
23	Correct	15 ms	2428 KB	Output is correct
24	Correct	15 ms	2480 KB	Output is correct
25	Correct	17 ms	2712 KB	Output is correct
26	Correct	5 ms	936 KB	Output is correct
27	Correct	4 ms	588 KB	Output is correct
28	Correct	1 ms	460 KB	Output is correct
29	Correct	17 ms	2660 KB	Output is correct
30	Correct	248 ms	70648 KB	Output is correct
31	Correct	251 ms	70496 KB	Output is correct
32	Correct	166 ms	65620 KB	Output is correct
33	Execution timed out	2081 ms	881904 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-