Submission #805201

#TimeUsernameProblemLanguageResultExecution timeMemory
805201EllinorAncient Books (IOI17_books)C++14
50 / 100
121 ms14188 KiB
#include <bits/stdc++.h> #include <unordered_map> using namespace std; #define rep(i,a,b) for (int i = (a); i < (b); i++) #define pb push_back typedef long long ll; typedef pair<int, int> pii; #include "books.h" long long minimum_walk(std::vector<int> p, int s) { int cycles = 0; vector<int> cycle(p.size(), -1); vector<pii> lohi; ll base = 0; rep(i,0,p.size()) { if (p[i] == i) cycle[i] = -1; else if (cycle[i] == -1) { cycle[i] = cycles; base += abs(i - p[i]); int at = p[i], low = i, high = i; while (at != i) { if (at < low) low = at; if (at > high) high = at; base += abs(at - p[at]); cycle[at] = cycles; at = p[at]; } lohi.pb(make_pair(low, high)); cycles++; } } ll add = 0; if (s == 0) { int low = 0, high = 0; // inc //int ind = 0; rep(i,0,cycle.size()) { if (cycle[i] == -1) continue; if (i > high) add += (i - high) * 2; high = max(high, lohi[cycle[i]].second); } } else { vector<int> closest(cycle.size(), -1); if (cycle[0] == -1) closest[0] = -1; else closest[0] = 0; rep(i,1,s) { if (cycle[i] == -1) closest[i] = closest[i - 1]; else closest[i] = i; } if (cycle[cycle.size() - 1] == -1) closest[cycle.size() - 1] = -1; else closest[cycle.size() - 1] = cycle.size() - 1; for (int i = cycle.size() - 2; i > s; i--) { if (cycle[i] == -1) closest[i] = closest[i + 1]; else closest[i] = i; } // edges int low = s, high = s; if (cycle[s] != -1) { low = lohi[cycle[s]].first; high = lohi[cycle[s]].second; } // map<pii, ll> dp; // ?? priority_queue<array<ll, 3>> pq; pq.push({-0, low, high}); dp[make_pair(low, high)] = -1; while (!pq.empty()) { auto x = pq.top(); pq.pop(); ll steps = x[0]; steps = -steps; low = x[1]; high = x[2]; if (low == 0 && high == cycle.size() - 1) { add = steps; break; } // int go = -1; if (low > 0 && high < cycle.size() - 1) { if (closest[low - 1] == -1) { low = 0; // continue; } if (closest[high + 1] == -1) { high = cycle.size() - 1; // continue; } } if (low > 0 && high < cycle.size() - 1) { int low1 = low, high1 = high, steps1 = steps; go = closest[low - 1]; steps1 += (low - closest[low - 1]) * 2; low1 = min(low, lohi[cycle[go]].first); high1 = max(high, lohi[cycle[go]].second); if (dp[make_pair(low1, high1)] == 0) { dp[make_pair(low1, high1)] = steps1; pq.push({-steps1, low1, high1}); } // low1 = low, high1 = high, steps1 = steps; go = closest[high + 1]; steps1 += (closest[high + 1] - high) * 2; low1 = min(low, lohi[cycle[go]].first); high1 = max(high, lohi[cycle[go]].second); if (dp[make_pair(low1, high1)] == 0 || steps1 < dp[make_pair(low1, high1)]) // dp[make_pair(low1, high1)] == 0 { dp[make_pair(low1, high1)] = steps1; pq.push({-steps1, low1, high1}); } continue; } else if (high < cycle.size() - 1) { if (closest[high + 1] == -1) { add = steps; break; } go = closest[high + 1]; steps += (closest[high + 1] - high) * 2; } else if (low > 0) { if (closest[low - 1] == -1) { add = steps; break; } go = closest[low - 1]; steps += (low - closest[low - 1]) * 2; } if (go == -1) { add = steps; break; } low = min(low, lohi[cycle[go]].first); high = max(high, lohi[cycle[go]].second); // if (!(dp[make_pair(low, high)] == 0 || dp[make_pair(low, high)] > steps)) continue; // ?? dp[make_pair(low, high)] = steps; pq.push({-steps, low, high}); } // } ll ans = base + add; return ans; }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:21:2: note: in expansion of macro 'rep'
   21 |  rep(i,0,p.size())
      |  ^~~
books.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:54:3: note: in expansion of macro 'rep'
   54 |   rep(i,0,cycle.size())
      |   ^~~
books.cpp:52:7: warning: unused variable 'low' [-Wunused-variable]
   52 |   int low = 0, high = 0; // inc
      |       ^~~
books.cpp:113:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if (low == 0 && high == cycle.size() - 1)
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~
books.cpp:123:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             if (low > 0 && high < cycle.size() - 1)
      |                            ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    if (low > 0 && high < cycle.size() - 1)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:172:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |    else if (high < cycle.size() - 1)
      |             ~~~~~^~~~~~~~~~~~~~~~~~
#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...