test/yukicoder/261.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/261

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• 離散対数 (src/Math/DiscreteLogarithm.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/261
// competitive-verifier: TLE 3
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <numeric>
#include "src/Math/DiscreteLogarithm.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> p(N);
 iota(p.begin(), p.end(), 0);
 int K;
 cin >> K;
 while (K--) {
  int X, Y;
  cin >> X >> Y;
  swap(p[--X], p[--Y]);
 }
 auto f= [](const vector<int> &l, const vector<int> &r) {
  const int n= l.size();
  vector<int> ret(n);
  for (int i= 0; i < n; ++i) ret[i]= r[l[i]];
  return ret;
 };
 DiscreteLogarithm log(f, f, [](const vector<int> &x) { return x[0]; }, 1e9);
 int Q;
 cin >> Q;
 while (Q--) {
  vector<int> A(N);
  for (int i= 0; i < N; ++i) cin >> A[i], --A[i];
  auto ans= log(p, p, A) + 1;
  cout << (ans ? ans : -1) << '\n';
 }
 return 0;
}

#line 1 "test/yukicoder/261.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/261
// competitive-verifier: TLE 3
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <numeric>
#line 2 "src/Math/DiscreteLogarithm.hpp"
#include <cmath>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 5 "src/Math/DiscreteLogarithm.hpp"
// mp : E × T -> T
// op : E × E -> E
// hash : T -> int
// s,t ∈ T, x ∈ E
// return min{ i : x^i(s) = t and i ∈ [0,N) } or -1 (not found)
template <class F, class G, class H> class DiscreteLogarithm {
 const F &mp;
 const G &op;
 const H &hash;
 const int64_t lim;
 using T= result_type_t<F>;
 using E= result_type_t<G>;
public:
 DiscreteLogarithm(const F &mp, const G &op, const H &hash, int64_t lim= 1ll << 50): mp(mp), op(op), hash(hash), lim(lim) { static_assert(std::is_convertible_v<std::invoke_result_t<H, T>, int>); }
 int64_t operator()(const E &x, T s, const T &t, int64_t N= -1) const {
  if (N < 0) N= lim;
  const int m= 1 << std::__lg(int(std::sqrt(N) + 1)), mask= m - 1;
  std::vector<T> val(m), vs(m);
  std::vector<int> os(m + 1), so(m);
  T s1= t;
  for (int i= 0; i < m; ++i) ++os[so[i]= hash(val[i]= s1= mp(x, s1)) & mask];
  for (int i= 0; i < m; ++i) os[i + 1]+= os[i];
  for (int i= 0; i < m; ++i) vs[--os[so[i]]]= val[i];
  E y= x;
  for (int k= m; k>>= 1;) y= op(y, y);
  bool failed= false;
  for (int64_t n= 0;; s= s1) {
   for (int a= hash(s1= mp(y, s)) & mask, j= os[a]; j < os[a + 1]; ++j) {
    if (s1 == vs[j]) {
     for (int i= 0;; s= mp(x, s)) {
      if (s == t) return n + i < N ? n + i : -1;
      if (++i == m) break;
     }
     if (failed) return -1;
     failed= true;
     break;
    }
   }
   if ((n+= m) >= N) break;
  }
  return -1;
 }
};
#line 8 "test/yukicoder/261.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> p(N);
 iota(p.begin(), p.end(), 0);
 int K;
 cin >> K;
 while (K--) {
  int X, Y;
  cin >> X >> Y;
  swap(p[--X], p[--Y]);
 }
 auto f= [](const vector<int> &l, const vector<int> &r) {
  const int n= l.size();
  vector<int> ret(n);
  for (int i= 0; i < n; ++i) ret[i]= r[l[i]];
  return ret;
 };
 DiscreteLogarithm log(f, f, [](const vector<int> &x) { return x[0]; }, 1e9);
 int Q;
 cin >> Q;
 while (Q--) {
  vector<int> A(N);
  for (int i= 0; i < N; ++i) cin >> A[i], --A[i];
  auto ans= log(p, p, A) + 1;
  cout << (ans ? ans : -1) << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	0_sample_1.txt	AC	1381 ms	5 MB
g++-13	0_sample_2.txt	AC	2061 ms	6 MB
g++-13	0_sample_3.txt	AC	42 ms	6 MB
g++-13	manual_1.txt	AC	47 ms	18 MB
g++-13	manual_2.txt	AC	47 ms	6 MB
g++-13	manual_3.txt	AC	43 ms	6 MB
g++-13	manual_4.txt	AC	88 ms	18 MB
g++-13	random_1.txt	AC	34 ms	17 MB
g++-13	random_10.txt	AC	57 ms	16 MB
g++-13	random_11.txt	AC	65 ms	18 MB
g++-13	random_12.txt	AC	39 ms	16 MB
g++-13	random_13.txt	AC	59 ms	17 MB
g++-13	random_14.txt	AC	46 ms	18 MB
g++-13	random_15.txt	AC	54 ms	17 MB
g++-13	random_16.txt	AC	42 ms	18 MB
g++-13	random_17.txt	AC	40 ms	18 MB
g++-13	random_18.txt	AC	208 ms	18 MB
g++-13	random_19.txt	AC	51 ms	18 MB
g++-13	random_2.txt	AC	25 ms	7 MB
g++-13	random_20.txt	AC	47 ms	18 MB
g++-13	random_21.txt	AC	108 ms	18 MB
g++-13	random_22.txt	AC	65 ms	18 MB
g++-13	random_23.txt	AC	134 ms	18 MB
g++-13	random_24.txt	AC	113 ms	18 MB
g++-13	random_25.txt	AC	392 ms	18 MB
g++-13	random_26.txt	AC	88 ms	18 MB
g++-13	random_27.txt	AC	65 ms	17 MB
g++-13	random_28.txt	AC	118 ms	17 MB
g++-13	random_29.txt	AC	120 ms	18 MB
g++-13	random_3.txt	AC	29 ms	9 MB
g++-13	random_30.txt	AC	1630 ms	18 MB
g++-13	random_4.txt	AC	185 ms	7 MB
g++-13	random_5.txt	AC	346 ms	8 MB
g++-13	random_6.txt	AC	27 ms	9 MB
g++-13	random_7.txt	AC	189 ms	10 MB
g++-13	random_8.txt	AC	56 ms	18 MB
g++-13	random_9.txt	AC	39 ms	18 MB
g++-13	special_1.txt	AC	712 ms	18 MB
g++-13	special_2.txt	AC	601 ms	18 MB
g++-13	special_3.txt	AC	302 ms	18 MB
clang++-18	0_sample_1.txt	AC	1474 ms	6 MB
clang++-18	0_sample_2.txt	AC	1963 ms	6 MB
clang++-18	0_sample_3.txt	AC	12 ms	6 MB
clang++-18	manual_1.txt	AC	41 ms	18 MB
clang++-18	manual_2.txt	AC	21 ms	6 MB
clang++-18	manual_3.txt	AC	19 ms	6 MB
clang++-18	manual_4.txt	AC	82 ms	18 MB
clang++-18	random_1.txt	AC	30 ms	17 MB
clang++-18	random_10.txt	AC	50 ms	16 MB
clang++-18	random_11.txt	AC	56 ms	18 MB
clang++-18	random_12.txt	AC	34 ms	16 MB
clang++-18	random_13.txt	AC	49 ms	17 MB
clang++-18	random_14.txt	AC	39 ms	18 MB
clang++-18	random_15.txt	AC	48 ms	17 MB
clang++-18	random_16.txt	AC	37 ms	18 MB
clang++-18	random_17.txt	AC	35 ms	18 MB
clang++-18	random_18.txt	AC	212 ms	18 MB
clang++-18	random_19.txt	AC	46 ms	18 MB
clang++-18	random_2.txt	AC	25 ms	7 MB
clang++-18	random_20.txt	AC	42 ms	18 MB
clang++-18	random_21.txt	AC	107 ms	18 MB
clang++-18	random_22.txt	AC	57 ms	18 MB
clang++-18	random_23.txt	AC	122 ms	18 MB
clang++-18	random_24.txt	AC	102 ms	18 MB
clang++-18	random_25.txt	AC	404 ms	18 MB
clang++-18	random_26.txt	AC	84 ms	18 MB
clang++-18	random_27.txt	AC	57 ms	17 MB
clang++-18	random_28.txt	AC	116 ms	18 MB
clang++-18	random_29.txt	AC	115 ms	18 MB
clang++-18	random_3.txt	AC	26 ms	9 MB
clang++-18	random_30.txt	AC	1628 ms	18 MB
clang++-18	random_4.txt	AC	189 ms	7 MB
clang++-18	random_5.txt	AC	370 ms	8 MB
clang++-18	random_6.txt	AC	25 ms	9 MB
clang++-18	random_7.txt	AC	186 ms	10 MB
clang++-18	random_8.txt	AC	52 ms	18 MB
clang++-18	random_9.txt	AC	36 ms	18 MB
clang++-18	special_1.txt	AC	765 ms	18 MB
clang++-18	special_2.txt	AC	603 ms	18 MB
clang++-18	special_3.txt	AC	299 ms	18 MB

Back to top page