Submission #7780618

---

Source Code Expand

// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^
using ll = long long;
using ld = long double;

template <int M, bool IsPrime = false> class Modulo {
  int n;
  static typename std::enable_if<IsPrime, ll>::type inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
  }

public:
  Modulo() : n(0) { ; }
  Modulo(int m) : n(m) {
    if (n >= M)
      n %= M;
    else if (n < 0)
      n = (n % M + M) % M;
  }
  Modulo(ll m) {
    if (m >= M)
      m %= M;
    else if (m < 0)
      m = (m % M + M) % M;
    n = m;
  }
  explicit operator int() const { return n; }
  explicit operator ll() const { return n; }
  bool operator==(const Modulo &a) const { return n == a.n; }
  Modulo &operator+=(const Modulo &a) {
    n += a.n;
    if (n >= M) n -= M;
    return *this;
  }
  Modulo &operator-=(const Modulo &a) {
    n -= a.n;
    if (n < 0) n += M;
    return *this;
  }
  Modulo &operator*=(const Modulo &a) {
    n = (ll(n) * a.n) % M;
    return *this;
  }
  Modulo operator+(const Modulo &a) const {
    Modulo res = *this;
    return res += a;
  }
  Modulo operator-(const Modulo &a) const {
    Modulo res = *this;
    return res -= a;
  }
  Modulo operator-() const { return Modulo(0) - *this; }
  Modulo operator*(const Modulo &a) const {
    Modulo res = *this;
    return res *= a;
  }

  Modulo operator^(ll m) const {
    if (m == 0) return Modulo(1);
    const Modulo a = *this;
    Modulo res = (a * a) ^ (m / 2);
    return m % 2 ? res * a : res;
  }
  typename std::enable_if<IsPrime, Modulo>::type
  operator/(const Modulo &a) const {
    return *this * inv(ll(a), M);
  }
  typename std::enable_if<IsPrime, Modulo>::type operator/=(const Modulo &a) {
    return *this *= inv(ll(a), M);
  }

  friend bool is_zero(const Modulo &x) { return int(x) == 0; }
  friend int abs(const Modulo &x) { return int(x); }

  static Modulo fact(int n, bool sw = true) {
    static std::vector<Modulo> v1 = { 1 }, v2 = { 1 };
    if (n >= (int)v1.size()) {
      const int from = v1.size(), to = n + 1024;
      v1.reserve(to);
      v2.reserve(to);
      for (int i = from; i < to; ++i) {
        v1.push_back(v1.back() * Modulo<M, true>(i));
        v2.push_back(v2.back() / Modulo<M, true>(i));
      }
    }
    return sw ? v1[n] : v2[n];
  }
  static Modulo comb(int a, int b) {
    if (b < 0 || b > a) return 0;
    return Modulo::fact(a, true) * Modulo::fact(b, false) *
           Modulo::fact(a - b, false);
  }
};

template <int prim_root, int mod, int sign>
void FMT(std::vector<Modulo<mod, true>> &a) {
  using mod_t = Modulo<mod, true>;
  const int n = a.size();
  mod_t h = mod_t(prim_root) ^ ((mod - 1) / n);
  if (sign == -1) h = mod_t(1) / h;
  int x = 0;
  for (int i = 1; i < n - 1; ++i) {
    for (int j = n / 2; j > (x ^= j); j /= 2)
      ;
    if (i < x) std::swap(a[x], a[i]);
  }
  for (int m = 1; m < n; m *= 2) {
    const int m2 = 2 * m;
    const mod_t base = mod_t(h) ^ (n / m2);
    mod_t w = 1;
    for (int i = 0; i < m; ++i) {
      for (int j = i; j < n; j += m2) {
        const mod_t u = a[j], d = a[j + m] * w;
        a[j] = u + d;
        a[j + m] = u - d;
      }
      w *= base;
    }
  }
}

template <int prim_root, int mod>
std::vector<Modulo<mod, true>> convolution(std::vector<Modulo<mod, true>> a,
                                           std::vector<Modulo<mod, true>> b) {
  using mod_t = Modulo<mod, true>;
  int size = a.size() + b.size();
  while ((size & -size) != size) size += (size & -size);
  a.resize(size);
  FMT<prim_root, mod, 1>(a);
  b.resize(size);
  FMT<prim_root, mod, 1>(b);
  for (int i = 0; i < size; ++i) a[i] *= b[i];
  FMT<prim_root, mod, -1>(a);
  const mod_t inv = mod_t(1) / mod_t(size);
  for (auto &x : a) x *= inv;
  return a;
}

constexpr ll M = 1000000;

using Mod = Modulo<998244353, true>;

vector<bool> solve(const vector<ll>& a) {
  vector<Mod> x(M+1, 0), y(M+1, 0);
  each(v, a) {
    x[v] = 1;
    y[M-v] = 1;
  }
  vector<Mod> v = convolution<3>(x, y);
  vector<bool> res(v.size(), false);
  rep(i, M, v.size()) {
    if (int(v[i]) > 0) {
      res[i-M] = true;
    }
  }
  return res;
}

void find_ans(vector<ll>& a, vector<ll>& b, ll x) {
  vector<P> va, vb;
  rep(i, a.size()) va.eb(a[i], i);
  rep(i, b.size()) vb.eb(b[i], i);
  sort(all(va));
  sort(all(vb));
  vector<ll> ans(4, -1);
  rep(i, a.size()) {
    auto it = lower_bound(all(va), P(a[i] + x, 0));
    if (it != va.end() && it->first == a[i] + x) {
      ans[0] = i, ans[2] = it->second;
      break;
    }
  }
  rep(i, b.size()) {
    auto it = lower_bound(all(vb), P(b[i] + x, 0));
    if (it != vb.end() && it->first == b[i] + x) {
      ans[3] = i, ans[1] = it->second;
      break;
    }
  }
  rep(i, 4) assert(ans[i] >= 0);
  cout << ans << endl;
}

void solve() {
  ll n, m; cin >> n >> m;
  vector<ll> a(n), b(m); cin >> a >> b;
  vector<bool> x = solve(a);
  vector<bool> y = solve(b);
  rep(i, 1, x.size()) {
    if (x[i] && i < y.size() && y[i]) {
      find_ans(a, b, i);
      return;
    }
  }
  cout << -1 << endl;
}

Submission Info

Judge Result