oj.uz

Submission #240048

# Submission time Handle Problem Language Result Execution time Memory
240048 2020-06-17T20:09:59 Z Jatana Ancient Books (IOI17_books) C++17
0 / 100
 2000 ms 1792 KB 
#include "books.h"
#include <vector>
#include <algorithm>
#include <iostream>

#define pb push_back
#define le(v) ((int)v.size())

using namespace std;
typedef long long ll;

int dp(vector<int> p, int s, int end) {
	if (is_sorted(p.begin(), p.end())) {
		return abs(s - end);
	} else {
		int rez = 1e9;
		for (int i = 0; i < le(p); i++) {
			if (p[i] != i) {
				int cur = abs(i - s);
				vector<int> q = p;
				int t = q[i];
				vector<int> ind{i};
				while (t != i) {
					ind.pb(t);
					t = q[t];
				}
				// for (int x : ind) {
				// 	cout << x << " ";
				// }
				// cout << endl;
				for (int i = 0; i < le(ind); i++) {
					int j = (i + 1) % le(ind);
					cur += abs(ind[i] - ind[j]);
				}
				sort(ind.begin(), ind.end());
				for (int x : ind) {
					q[x] = x;
				}	
				cur += dp(q, i, end);
				rez = min(rez, cur);
			}
		}
		return rez;
	}
}

ll minimum_walk(vector<int> p, int s) {
	return dp(p, s, s);
	ll rez = 0;
	while (!is_sorted(p.begin(), p.end())) {
		if (p[s] == s) {
			s++; rez++;
		} else {
			int t = p[s];
			vector<int> ind{s};
			while (t != s) {
				ind.pb(t);
				t = p[t];
			}
			// for (int x : ind) {
			// 	cout << x << " ";
			// }
			// cout << endl;
			for (int i = 0; i < le(ind); i++) {
				int j = (i + 1) % le(ind);
				rez += abs(ind[i] - ind[j]);
			}
			sort(ind.begin(), ind.end());
			for (int x : ind) {
				p[x] = x;
			}	
		}
	}
	rez += s;
	return rez;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Incorrect 5 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Incorrect 5 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Incorrect 5 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Incorrect 5 ms 256 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -