Submission #598218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
598218	2022-07-17T19:52:21 Z	yanndev	Ancient Books (IOI17_books)	C++17	12 / 100	2000 ms	484 KB

books

#include <bits/stdc++.h>
#define ll long long
using namespace std;

map<pair<vector<int>, pair<int, int>>, pair<bool, ll>> vis {};

ll recSolve(int pos, vector<int> vals, int carry, int dep) {
	if (pos >= (int)vals.size() || pos < 0)
		return 1e9;
	if (dep > 15)
		return 1e9;
	/*if (vis[{vals, {pos, carry}}].first)
		return vis[{vals, {pos, carry}}].second;*/

	ll mnAns = 1e9;
	//vis[{vals, {pos, carry}}] = {true, 1e9};

	bool ok = true;
	for (int i = 0; i < (int)vals.size(); i++)
		if (vals[i] != i)
			ok = false;
	if (ok) {
		//printf("food bruh %d %d\n", pos);
		vis[{vals, {pos, carry}}] = {true, pos};
		return pos;
	}

	mnAns = min(mnAns, 1 + recSolve(pos + 1, vals, carry, dep + 1));
	mnAns = min(mnAns, 1 + recSolve(pos - 1, vals, carry, dep + 1));

	int old = vals[pos];
	vals[pos] = carry;
	mnAns = min(mnAns, recSolve(pos, vals, old, dep + 1));
	vals[pos] = old;
	//vis[{vals, {pos, carry}}] = {true, mnAns};
	return mnAns;
}

ll minimum_walk(vector<int> p, int s) {
    int n = (int)p.size();
	return recSolve(0, p, -1, 0);
    /*vector<vector<int>> cycles {};
    vector<bool> vis (n, false);

    for (int i = 0; i < n; i++) {
        if (vis[i])
            continue;
        
        //ans += abs(i - last);
        int pos = i;
        cycles.push_back({});
        while (!vis[pos]) {
            vis[pos] = true;
            cycles.back().push_back(pos);
            //ans += abs(p[pos] - pos);
            pos = p[pos];
        }
    }

    //ans += last;
	vector<int> perm {};
	for (int i = 0; i < (int)cycles.size(); i++)
		perm.push_back(i);
	do {
		ll sub = 0;
		int lst = 0;
		for (int i = 0; i < (int)cycles.size(); i++) {
			for (auto& x: cycles[i]) {
				sub += abs(x - lst);
				lst = x;
			}
		}
		sub += lst;
		ans = min(ans, sub);
	} while (next_permutation(perm.begin(), perm.end()));
    return ans;*/
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:40:9: warning: unused variable 'n' [-Wunused-variable]
   40 |     int n = (int)p.size();
      |         ^

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	276 KB	Output is correct
2	Correct	214 ms	272 KB	Output is correct
3	Correct	208 ms	272 KB	Output is correct
4	Correct	76 ms	284 KB	Output is correct
5	Correct	204 ms	280 KB	Output is correct
6	Correct	219 ms	280 KB	Output is correct
7	Correct	191 ms	276 KB	Output is correct
8	Correct	220 ms	280 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	179 ms	280 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	5 ms	212 KB	Output is correct
13	Correct	200 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	190 ms	280 KB	Output is correct
16	Correct	192 ms	212 KB	Output is correct
17	Correct	186 ms	280 KB	Output is correct
18	Correct	177 ms	296 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	276 KB	Output is correct
2	Correct	214 ms	272 KB	Output is correct
3	Correct	208 ms	272 KB	Output is correct
4	Correct	76 ms	284 KB	Output is correct
5	Correct	204 ms	280 KB	Output is correct
6	Correct	219 ms	280 KB	Output is correct
7	Correct	191 ms	276 KB	Output is correct
8	Correct	220 ms	280 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	179 ms	280 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	5 ms	212 KB	Output is correct
13	Correct	200 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	190 ms	280 KB	Output is correct
16	Correct	192 ms	212 KB	Output is correct
17	Correct	186 ms	280 KB	Output is correct
18	Correct	177 ms	296 KB	Output is correct
19	Execution timed out	2086 ms	364 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	276 KB	Output is correct
2	Correct	214 ms	272 KB	Output is correct
3	Correct	208 ms	272 KB	Output is correct
4	Correct	76 ms	284 KB	Output is correct
5	Correct	204 ms	280 KB	Output is correct
6	Correct	219 ms	280 KB	Output is correct
7	Correct	191 ms	276 KB	Output is correct
8	Correct	220 ms	280 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	179 ms	280 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	5 ms	212 KB	Output is correct
13	Correct	200 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	190 ms	280 KB	Output is correct
16	Correct	192 ms	212 KB	Output is correct
17	Correct	186 ms	280 KB	Output is correct
18	Correct	177 ms	296 KB	Output is correct
19	Execution timed out	2086 ms	364 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2060 ms	484 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	276 KB	Output is correct
2	Correct	214 ms	272 KB	Output is correct
3	Correct	208 ms	272 KB	Output is correct
4	Correct	76 ms	284 KB	Output is correct
5	Correct	204 ms	280 KB	Output is correct
6	Correct	219 ms	280 KB	Output is correct
7	Correct	191 ms	276 KB	Output is correct
8	Correct	220 ms	280 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	179 ms	280 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	5 ms	212 KB	Output is correct
13	Correct	200 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	190 ms	280 KB	Output is correct
16	Correct	192 ms	212 KB	Output is correct
17	Correct	186 ms	280 KB	Output is correct
18	Correct	177 ms	296 KB	Output is correct
19	Execution timed out	2086 ms	364 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-