Submission #1082986

#TimeUsernameProblemLanguageResultExecution timeMemory
1082986happypotatoAncient Books (IOI17_books)C++17
12 / 100
4 ms4188 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define ff first #define ss second #define pb push_back long long st123(vector<int> p, int s) { vector<int> ori = p; int n = (int)(p.size()); ll ans = 0; for (int i = 0; i < n; i++) { if (p[i] == -1 || p[i] == i) continue; int cur = i; vector<int> seq = {cur}; while (p[cur] != i) { cur = p[cur]; seq.pb(cur); } // cerr << i << ": "; // for (int x : seq) cerr << x << ' '; // cerr << endl; for (int i = 0; i < (int)(seq.size()); i++) { ans += abs(seq[(i + 1) % (int)(seq.size())] - seq[i]); p[seq[i]] = -1; } } vector<int> bruh; int maxi = 0; for (int i = 0; i < n; i++) { maxi = max(maxi, ori[i]); if (maxi == i) bruh.pb(i); } // for (int x : bruh) cerr << x << ' '; // cerr << endl; while (bruh.size() >= 2) { int x = bruh.size(); if (bruh[x - 1] - bruh[x - 2] == 1) { bruh.pop_back(); } else break; } ans += ((int)(bruh.size()) - 1) * 2; return ans; } long long minimum_walk(vector<int> p, int s) { // if (s == 0) return st123(p, s); vector<int> ori = p; int n = (int)(p.size()); ll ans = 0; vector<pii> range(n); for (int i = 0; i < n; i++) { if (p[i] == -1) continue; int cur = i; vector<int> seq = {cur}; while (p[cur] != i) { cur = p[cur]; seq.pb(cur); } pii get = {i, i}; for (int x : seq) { get.ff = min(get.ff, x); get.ss = max(get.ss, x); } // cerr << "seq: "; // for (int x : seq) cerr << x << ' '; // cerr << " | " << get.ff << ' ' << get.ss << endl; for (int j = 0; j < (int)(seq.size()); j++) { ans += abs(seq[(j + 1) % (int)(seq.size())] - seq[j]); range[seq[j]] = get; p[seq[j]] = -1; } } // for (int i = 0; i < n; i++) { // cerr << i << ": " << range[i].ff << ' ' << range[i].ss << endl; // } vector<vector<int>> dp(n); for (int i = 0; i < n; i++) dp[i].resize(n, 1e9); dp[range[s].ff][range[s].ss] = 0; queue<pii> q; q.push(range[s]); while (!q.empty()) { pii cur = q.front(); q.pop(); if (cur.ff > 0) { pii nrange = {range[cur.ff - 1].ff, max(cur.ss, range[cur.ff - 1].ss)}; if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss] + 1) { dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss] + 1; q.push(nrange); } } if (cur.ss < n - 1) { pii nrange = {min(cur.ff, range[cur.ss + 1].ff), range[cur.ss + 1].ss}; if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss] + 1) { dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss] + 1; q.push(nrange); } } } int lb = 0, rb = n - 1; while (lb < n && ori[lb] == lb) lb++; if (lb == n) return 0; while (rb >= 0 && ori[rb] == rb) rb--; int take = 1e9; for (int i = 0; i <= lb; i++) { for (int j = rb; j < n; j++) take = min(take, dp[i][j]); } ans += take * 2; return ans; }
#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...