Submission #21282507


Source Code Expand

Copy
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "atcoder/all"

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};

constexpr int N = 2 * 100'000;
constexpr int P = 1'000'000 + 3;
constexpr int K = 4 * 10'000;
using Mint = ModInt<P>;

bool isDistinct(const vector<int> &as) {
  return (set<int>(as.begin(), as.end()).size() == as.size());
}
bool isDistinct(const vector<Mint> &as) {
  vector<int> bs;
  for (const Mint a : as) {
    bs.push_back(a.x);
  }
  return isDistinct(bs);
}

int main() {
  scanf("%*d%*d%*d");
  vector<Mint> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    int x;
    scanf("%d", &x);
    A[i] = x;
  }
  for (int i = 0; i < N; ++i) {
    int x;
    scanf("%d", &x);
    B[i] = x;
  }
  vector<int> L(K), R(K);
  for (int k = 0; k < K; ++k) {
    scanf("%d%d", &L[k], &R[k]);
    --L[k];
    --R[k];
  }
  
  vector<vector<int>> G(K);
  for (int k = 0; k < K; ++k) {
    G[L[k]].push_back(k);
    G[R[k]].push_back(k);
  }
  vector<int> vis(K, 0);
  vector<vector<int>> cycs;
  for (int k = 0; k < K; ++k) {
    if (!vis[k]) {
      vector<int> cyc;
      for (int u = L[k], l = k; ; ) {
        vis[l] = true;
        cyc.push_back(l);
        const int v = L[l] ^ R[l] ^ u;
        const int ll = G[v][0] ^ G[v][1] ^ l;
        u = v;
        l = ll;
        if (l == k) {
          break;
        }
      }
      cycs.push_back(cyc);
    }
  }
  sort(cycs.begin(), cycs.end(), [&](const vector<int> &cyc0, const vector<int> &cyc1) {
    const int sz0 = cyc0.size();
    const int sz1 = cyc1.size();
    return (((sz0 & 1) != (sz1 & 1)) ? ((sz0 & 1) > (sz1 & 1)) : (sz0 > sz1));
  });
  
  vector<Int> freqA(P + 1, 0), freqB(P + 1, 0);
  for (int i = 0; i < N; ++i) ++freqA[A[i].x];
  for (int i = 0; i < N; ++i) ++freqB[P - B[i].x];
  const auto prod = atcoder::convolution_ll(freqA, freqB);
  vector<Int> freqAB(P, 0);
  for (int x = 0; x < (int)prod.size(); ++x) {
    freqAB[x % P] += prod[x];
  }
  const Mint d = (int)(max_element(freqAB.begin(), freqAB.end()) - freqAB.begin());
  assert(freqAB[d.x] >= K);
  vector<int> idsA(P, -1), idsB(P, -1);
  for (int i = 0; i < N; ++i) idsA[A[i].x] = i;
  for (int i = 0; i < N; ++i) idsB[B[i].x] = i;
  vector<pair<int, int>> ps;
  for (int iA = 0; iA < N; ++iA) {
    const int iB = idsB[(A[iA] - d).x];
    if (iB != -1) {
      ps.emplace_back(iA, iB);
    }
  }
  assert((int)ps.size() == freqAB[d.x]);
  int pos = 0;
  
  vector<Mint> C(K);
  vector<int> S(K), T(K);
  for (const auto &cyc : cycs) {
    const int len = cyc.size();
    vector<int> us(len + 1);
    us[0] = L[cyc[0]];
    for (int j = 0; j < len; ++j) {
      us[j + 1] = L[cyc[j]] ^ R[cyc[j]] ^ us[j];
    }
    assert(us[len] == us[0]);
    for (int j = 0; j < len; ++j) {
      S[cyc[j]] = ps[pos].first;
      T[cyc[(j + 1) % len]] = ps[pos].second;
      C[us[(j + 1) % len]] = A[S[cyc[j]]] - d / 2;
      ++pos;
    }
  }
  
  for (int k = 0; k < K; ++k) {
    if (k > 0) printf(" ");
    printf("%u", C[k] ? C[k].x : P);
  }
  puts("");
  for (int k = 0; k < K; ++k) {
    printf("%d %d\n", S[k] + 1, T[k] + 1);
  }
  
  assert(isDistinct(C));
  assert(isDistinct(S));
  assert(isDistinct(T));
  for (int k = 0; k < K; ++k) {
    assert(A[S[k]] + B[T[k]] == C[L[k]] + C[R[k]]);
  }
  return 0;
}

Submission Info

Submission Time
Task K - Special Chopsticks
User hos_lyric
Language C++ (GCC 9.2.1)
Score 100
Code Size 6576 Byte
Status AC
Exec Time 816 ms
Memory 96400 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:90:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%*d%*d%*d");
      |   ~~~~~^~~~~~~~~~~~~
./Main.cpp:94:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   94 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
./Main.cpp:99:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   99 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
./Main.cpp:104:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%d%d", &L[k], &R[k]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 65
Set Name Test Cases
All Arithmetic2_00, Arithmetic5_00, Arithmetic5_01, Arithmetic5_02, Arithmetic5_03, Arithmetic5_04, Arithmetic5_05, Arithmetic5_06, Arithmetic5_07, Arithmetic5_08, Arithmetic5_09, Arithmetic5_10, Arithmetic5_11, ArithmeticMod_00, ArithmeticMod_01, ArithmeticMod_02, ArithmeticMod_03, ArithmeticMod_04, ArithmeticMod_05, ArithmeticMod_06, ArithmeticMod_07, ArithmeticMod_08, ArithmeticMod_09, ArithmeticMod_10, ArithmeticMod_11, ArithmeticMod_12, ArithmeticMod_13, ArithmeticMod_14, ArithmeticMod_15, ArithmeticMod_16, ArithmeticMod_17, ArithmeticMod_18, ArithmeticMod_19, ArithmeticMod_20, ArithmeticMod_21, ArithmeticMod_22, ArithmeticMod_23, ArithmeticMod_24, ArithmeticMod_25, ArithmeticMod_26, ArithmeticMod_27, ArithmeticMod_28, ArithmeticMod_29, extreme_00, random_00, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, random_16, random_17, random_18, random_19, special_00
Case Name Status Exec Time Memory
Arithmetic2_00 AC 811 ms 94380 KB
Arithmetic5_00 AC 809 ms 94280 KB
Arithmetic5_01 AC 808 ms 94224 KB
Arithmetic5_02 AC 811 ms 94284 KB
Arithmetic5_03 AC 809 ms 94388 KB
Arithmetic5_04 AC 811 ms 94328 KB
Arithmetic5_05 AC 806 ms 94284 KB
Arithmetic5_06 AC 807 ms 94384 KB
Arithmetic5_07 AC 807 ms 94320 KB
Arithmetic5_08 AC 804 ms 94176 KB
Arithmetic5_09 AC 806 ms 94292 KB
Arithmetic5_10 AC 804 ms 94284 KB
Arithmetic5_11 AC 805 ms 94288 KB
ArithmeticMod_00 AC 807 ms 94324 KB
ArithmeticMod_01 AC 816 ms 94392 KB
ArithmeticMod_02 AC 809 ms 94296 KB
ArithmeticMod_03 AC 810 ms 94184 KB
ArithmeticMod_04 AC 808 ms 94512 KB
ArithmeticMod_05 AC 807 ms 94396 KB
ArithmeticMod_06 AC 814 ms 94476 KB
ArithmeticMod_07 AC 808 ms 94448 KB
ArithmeticMod_08 AC 810 ms 94252 KB
ArithmeticMod_09 AC 813 ms 94180 KB
ArithmeticMod_10 AC 809 ms 94176 KB
ArithmeticMod_11 AC 810 ms 94260 KB
ArithmeticMod_12 AC 809 ms 94228 KB
ArithmeticMod_13 AC 810 ms 94224 KB
ArithmeticMod_14 AC 805 ms 94184 KB
ArithmeticMod_15 AC 807 ms 94324 KB
ArithmeticMod_16 AC 805 ms 94300 KB
ArithmeticMod_17 AC 804 ms 94424 KB
ArithmeticMod_18 AC 807 ms 94172 KB
ArithmeticMod_19 AC 805 ms 94296 KB
ArithmeticMod_20 AC 805 ms 94324 KB
ArithmeticMod_21 AC 807 ms 94288 KB
ArithmeticMod_22 AC 807 ms 94260 KB
ArithmeticMod_23 AC 807 ms 94436 KB
ArithmeticMod_24 AC 805 ms 94180 KB
ArithmeticMod_25 AC 805 ms 94384 KB
ArithmeticMod_26 AC 806 ms 94416 KB
ArithmeticMod_27 AC 799 ms 94184 KB
ArithmeticMod_28 AC 807 ms 94316 KB
ArithmeticMod_29 AC 804 ms 94184 KB
extreme_00 AC 799 ms 94180 KB
random_00 AC 803 ms 96336 KB
random_01 AC 806 ms 94404 KB
random_02 AC 803 ms 96312 KB
random_03 AC 799 ms 94300 KB
random_04 AC 801 ms 96332 KB
random_05 AC 805 ms 94468 KB
random_06 AC 806 ms 94300 KB
random_07 AC 802 ms 96308 KB
random_08 AC 806 ms 94352 KB
random_09 AC 802 ms 96400 KB
random_10 AC 803 ms 96268 KB
random_11 AC 805 ms 94404 KB
random_12 AC 804 ms 94388 KB
random_13 AC 804 ms 94404 KB
random_14 AC 800 ms 96336 KB
random_15 AC 804 ms 94224 KB
random_16 AC 800 ms 96348 KB
random_17 AC 805 ms 94288 KB
random_18 AC 804 ms 94312 KB
random_19 AC 800 ms 96300 KB
special_00 AC 797 ms 94388 KB