Untitled Diff
2 removals
134 lines
6 additions
136 lines
/*
/*
// sol used...
// sol used...
credits: @yash_daga
credits: @yash_daga
author : Aryan Agarwal, IIT KGP
author : Aryan Agarwal, IIT KGP
created : 18-December-2020 12:24:57 IST
created : 18-December-2020 12:24:57 IST
*/
*/
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std;
#define int long long
#define int long long
const int mxn = 1e5;
const int mxn = 1e5;
const long long INF = 2e18;
const long long INF = 2e18;
const int32_t M = 1000000007; /*more than (10)^9*/ /*7 + 1e9*/
const int32_t M = 1000000007; /*more than (10)^9*/ /*7 + 1e9*/
// const int32_t M = 998244353; /*less than (10)^9*/ /*1 + 7*17*(2)^23*/
// const int32_t M = 998244353; /*less than (10)^9*/ /*1 + 7*17*(2)^23*/
const long double pie = acos(-1);
const long double pie = acos(-1);
#define X first
#define X first
#define Y second
#define Y second
#define pb push_back
#define pb push_back
#define sz(a) ((int)(a).size())
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define all(a) (a).begin(), (a).end()
#define F(i, a, b) for (int i = a; i <= b; i++)
#define F(i, a, b) for (int i = a; i <= b; i++)
#define RF(i, a, b) for (int i = a; i >= b; i--)
#define RF(i, a, b) for (int i = a; i >= b; i--)
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
cout << name << " : " << arg1 << std::endl;
}
}
template <typename Arg1, typename... Args>
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
}
void solve()
void solve()
{
{
int n;
int n;
cin>>n;
cin>>n;
vector <int> b(n),a(n),cnt(2*n+1,0);
vector <int> b(n),a(n),cnt(2*n+1,0);
F(i,0,n-1){cin>>b[i];cnt[b[i]]++;}
F(i,0,n-1){cin>>b[i];cnt[b[i]]++;}
int ind=0;
int ind=0;
F(i,1,2*n)
F(i,1,2*n)
{
{
if(cnt[i]==0)a[ind++]=i;
if(cnt[i]==0)a[ind++]=i;
}
}
set<int> s[2][2];
set<int> s[2][2];
F(i,0,n-1)
F(i,0,n-1)
{
{
if(b[i]>a[i])
if(b[i]>a[i])
{
{
s[0][0].insert(b[i]);
s[0][0].insert(b[i]);
s[0][1].insert(a[i]);
s[0][1].insert(a[i]);
}
}
else
else
{
{
s[1][0].insert(b[i]);
s[1][0].insert(b[i]);
s[1][1].insert(a[i]);
s[1][1].insert(a[i]);
}
}
}
}
int ans=0;
int ans=0;
for(int x : s[0][0])
for(int x : s[0][0])
{
{
auto it=upper_bound(all(s[0][1]),x);
// auto it=upper_bound(all(s[0][1]),x);
auto it=s[0][1].upper_bound(x);
if(it!=s[0][1].end())
if(it!=s[0][1].end())
{
{
ans++;
ans++;
s[0][1].erase(it);
s[0][1].erase(it);
}
}
else
else
{
{
break;
break;
}
}
}
}
for(int x : s[1][1])
for(int x : s[1][1])
{
{
auto it=upper_bound(all(s[1][0]),x);
// auto it=upper_bound(all(s[1][0]),x);
auto it=s[1][0].upper_bound(x);
if(it!=s[1][0].end())
if(it!=s[1][0].end())
{
{
ans++;
ans++;
s[1][0].erase(it);
s[1][0].erase(it);
}
}
else
else
{
{
break;
break;
}
}
}
}
cout<<ans+1;
cout<<ans+1;
cout<<"\n";
cout<<"\n";
}
}
signed main()
signed main()
{
{
ios_base::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin.tie(NULL);
cout.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// freopen("output.txt","w",stdout);
#endif
#endif
#ifdef ARYAN_SIEVE
#ifdef ARYAN_SIEVE
// defualt mxn_sieve = 1e5
// defualt mxn_sieve = 1e5
sieve();
sieve();
#endif
#endif
#ifdef ARYAN_SEG_SIEVE
#ifdef ARYAN_SEG_SIEVE
// default [L,R] = [1,1e5]
// default [L,R] = [1,1e5]
segmented_sieve();
segmented_sieve();
#endif
#endif
#ifdef ARYAN_FACT
#ifdef ARYAN_FACT
// default mxn_fact = 1e5
// default mxn_fact = 1e5
fact_init();
fact_init();
#endif
#endif
// cout<<fixed<<setprecision(10);
// cout<<fixed<<setprecision(10);
int _t=1;
int _t=1;
cin>>_t;
cin>>_t;
for (int i=1;i<=_t;i++)
for (int i=1;i<=_t;i++)
{
{
// cout<<"Case #"<<i<<": ";
// cout<<"Case #"<<i<<": ";
solve();
solve();
}
}
return 0;
return 0;
}
}