Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Untitled Diff

Created Diff never expires
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;
}
}