QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#327402#7956. Walk SwappingckisekiCompile Error//C++233.2kb2024-02-14 23:12:122024-02-14 23:12:13

Judging History

你现在查看的是最新测评结果

  • [2024-02-14 23:12:13]
  • 评测
  • [2024-02-14 23:12:12]
  • 提交

answer

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("no-math-errno,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC target("popcnt,abm,mmx,avx")

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

#define all(x) begin(x),end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

namespace {
const int inf = 1e9;

int solve(int n, const auto &a, const auto &b) {
  if (a == b) return 0;

  vector<int> dpB(n * 2), dpA(n * 2);
  for (int i = n * 2 - 1; i >= 0; i--) {
    dpB[i] = (i + 1 < n * 2 ? dpB[i + 1] : 0) + 1;
    int x = i + 1, y = i;
    if (x >= n) x -= n;
    if (x >= n) x -= n;
    if (y >= n) y -= n;
    if (a[x] != b[y]) dpB[i] = 0;
  }

  vector<vector<int>> qs(n * 2);
  vector<int> cnt(n * 3);
  {
    int j = 0;
    for (int i = 0; i < n * 2; i++) {
      dpA[i] = j;
      if (i >= n) {
        ++cnt[i + n - j - 1];
        ++cnt[i - j - 1];
        // qs[i + n - j - 1].emplace_back(i);
        // qs[i - j - 1].emplace_back(i - n);
      }
      int x = i < n ? i : i - n;
      if (a[x] != b[x]) j = 0;
      else ++j;
    }
  }

  for (int i = 0; i < n * 2; i++)
    qs[i].reserve(cnt[i]);

  for (int i = 0; i < n * 2; i++) {
    int z = n - dpA[i < n ? i + n : i];
    if (i + z - 1 < n * 2)
      qs[i + z - 1].emplace_back(i);
  }

  vector<int> idx(n, 1e9);
  /* vector<vector<int>> idx(n); */
  /* for (int i = 0; i < n * 2; i++) */
  /*   idx[b[i < n ? i : i - n]].push_back(i); */

  orange(all(a));
  orange(all(b));
  orange(all(dpA));
  orange(all(dpB));

  int ans = inf;

  for (int x = n * 2 - 1; x >= 0; x--) {
    idx[b[x < n ? x : x - n]] = x;
    for (int i : qs[x]) {
      int z = idx[a[i < n ? i : i - n]];
      if (z <= i + dpB[i])
        ans = min(ans, z - i);
    }
  }

  return ans;
}
}

signed main() {
  cin.tie(nullptr) -> sync_with_stdio(false);

  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int &x : a) cin >> x, --x;
  for (int &x : b) cin >> x, --x;

  /* debug(solve(n, a, b)); */
  /* return 0; */

  int ans = inf;
  for (int k = 0; k < n; k++) {
    ans = min(ans, k * (n - 1) + solve(n, a, b));
    int x = a[0];
    for (int j = 0; j + 1 < n; j++)
      a[j] = a[j + 1];
    a[n - 1] = x;
    // rotate(a.begin(), a.begin() + 1, a.end());
  }
  ranges::reverse(a);
  ranges::reverse(b);
  for (int k = 0; k < n; k++) {
    ans = min(ans, k * (n - 1) + solve(n, a, b));
    int x = a[0];
    for (int j = 0; j + 1 < n; j++)
      a[j] = a[j + 1];
    a[n - 1] = x;
    // rotate(a.begin(), a.begin() + 1, a.end());
  }

  if (ans == inf)
    ans = -1;
  cout << ans << '\n';
}

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~