Submission #240070

#TimeUsernameProblemLanguageResultExecution timeMemory
240070JatanaAncient Books (IOI17_books)C++17
0 / 100
8 ms384 KiB
#include "books.h" #include <vector> #include <algorithm> #include <iostream> #include <cassert> #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; int buf = -1; while (!is_sorted(p.begin(), p.end())) { // cout << buf << " " << s << endl; // for (int x : p) { // cout << x << " "; // } // cout << endl; if (buf == s) { swap(p[s], buf); } else if (buf < s) { swap(buf, p[s]); } if (buf == -1) { bool ok = true; for (int i = s; i < le(p); i++) { if (p[i] != i) { ok = false; } } if (ok) { s--; rez++; } else { s++; rez++; } } else { if (buf < s) { s--; } else s++; rez++; } } rez += s; return rez; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...