fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=3e5+15;
  49. const ll inf=5e16;
  50.  
  51. template<typename T> inline void add(T &x, const T &y)
  52. {
  53.     x+=y;
  54.     if(x>=mod) x-=mod;
  55.     if(x<0) x+=mod;
  56. }
  57.  
  58. template<typename T> inline bool maxi(T &a, T b)
  59. {
  60.     if(a>=b) return 0;
  61.     a=b; return 1;
  62. }
  63.  
  64. template<typename T> inline bool mini(T &a, T b)
  65. {
  66.     if(a<=b) return 0;
  67.     a=b; return 1;
  68. }
  69.  
  70. int n, m, a[maxn], b[maxn];
  71. vpii va, vb;
  72.  
  73. inline ll cal(int a, int b)
  74. {
  75.     if(b<0) a=-a, b=-b;
  76.     int g=__gcd(a, b);
  77.     return 1ll*(a/g)*mod+(b/g);
  78. }
  79.  
  80. struct myhash
  81. {
  82.     static uint64_t splitmix64(uint64_t x)
  83.     {
  84.         x+=0x9e3779b97f4a7c15ULL;
  85.         x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;
  86.         x=(x^(x>>27))*0x94d049bb133111ebULL;
  87.         return x^(x>>31);
  88.     }
  89.     size_t operator()(uint64_t x) const
  90.     {
  91.         static const uint64_t FIXED=chrono::steady_clock::now().time_since_epoch().count();
  92.         return splitmix64(x+FIXED);
  93.     }
  94. };
  95.  
  96. unordered_map<int, int, myhash> freq;
  97. unordered_map<ll, int, myhash> cnt;
  98.  
  99. signed main()
  100. {
  101.     rf();
  102.     int tt; cin>>tt;
  103.     while(tt--)
  104.     {
  105.         cin>>m>>n;
  106.         ff(i, 1, m) cin>>a[i];
  107.         ff(i, 1, n) cin>>b[i];
  108.  
  109.         cnt.clear(); va.clear(); vb.clear();
  110.         freq.clear(); freq.reserve(1000);
  111.         ff(i ,1, m) ++freq[a[i]];
  112.         for(auto x:freq) va.pb(x);
  113.         freq.clear(); freq.reserve(1000);
  114.         ff(i ,1, n) ++freq[b[i]];
  115.         for(auto x:freq) vb.pb(x);
  116.         cnt.reserve(m*n);
  117.         for(auto x:va) for(auto y:vb) cnt[cal(x.fi, y.fi) ]+=min(x.se, y.se);
  118.         int ans=0;
  119.         for(auto x:cnt) maxi(ans, x.se);
  120.         cout<<m+n-ans<<nl;
  121.     }
  122.     re;
  123. }
  124.  
Success #stdin #stdout 0.01s 5640KB
comments (?)
stdin 
2


4 4
1 2 3 4
5 6 7 8


4 4
1 2 3 4
1 2 3 4
stdout 
6
4
https://ideone.com/ne6BCM
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!