Phoenix and Socks solution codeforces – To satisfy his love of matching socks, Phoenix has brought his nn socks 2021

  Phoenix and Socks solution codeforces

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

To satisfy his love of matching socks, Phoenix has brought his nn socks (nn is even) to the sock store. Each of his socks has a color cici and is either a left sock or right sock.

Phoenix can pay one dollar to the sock store to either:

  • recolor a sock to any color cc′ (1cn)(1≤c′≤n)
  • turn a left sock into a right sock
  • turn a right sock into a left sock

The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn’t change when it turns into a right sock, and vice versa.

A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make n/2n/2 matching pairs? Each sock must be included in exactly one matching pair.

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

Input Phoenix and Socks solution codeforces

The input consists of multiple test cases. The first line contains an integer tt (1t10001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers nnll, and rr (2n21052≤n≤2⋅105nn is even; 0l,rn0≤l,r≤nl+r=nl+r=n) — the total number of socks, and the number of left and right socks, respectively.

The next line contains nn integers cici (1cin1≤ci≤n) — the colors of the socks. The first ll socks are left socks, while the next rr socks are right socks.

It is guaranteed that the sum of nn across all the test cases will not exceed 21052⋅105.

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

Output Phoenix and Socks solution codeforces

For each test case, print one integer — the minimum cost for Phoenix to make n/2n/2 matching pairs. Each sock must be included in exactly one matching pair.

Example Phoenix and Socks solution codeforces

inputPhoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

Copy
4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3

outputPhoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

Copy
2
3
5
3
Note Phoenix and Socks solution codeforces

In the first test case, Phoenix can pay 22 dollars to:

  • recolor sock 11 to color 22
  • recolor sock 33 to color 22

There are now 33 matching pairs. For example, pairs (1,4)(1,4)(2,5)(2,5), and (3,6)(3,6) are matching.In the second test case, Phoenix can pay 33 dollars to:

  • turn sock 66 from a right sock to a left sock
  • recolor sock 33 to color 11
  • recolor sock 44 to color 11

There are now 33 matching pairs. For example, pairs (1,3)(1,3)(2,4)(2,4), and (5,6)(5,6) are matching.

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

PyPy 3

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

import sys
input=sys.stdin.buffer.readline

for t in range(int(input())):
N,L,R=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):
A[i]-=1
if L>R:
A=A[L:]+A[:L]
L,R=R,L
C=[0]*N
for i in range(L):
C[A[i]]+=1
for i in range(L,N):
C[A[i]]-=1
X=(R-L)>>1
Y=X
F=[0]*N
for i in range(L):
F[i]=1
for i in range(L,N):
if C[A[i]]<=-2 and X>0:
C[A[i]]+=2
X-=1
F[i]=1
#print(A,F,C)
print(Y+(sum([abs(C[i]) for i in range(N)])>>1))

C++

Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int cntl[N],cntr[N];

int main(){
int t;
cin>>t;
while(t--){
int n,l,r,x,ans=0;
cin>>n>>l>>r;
for(int i=1;i<=n;++i)
cntl[i]=cntr[i]=0;
for(int i=1;i<=l;++i)
cin>>x,cntl[x]++;
for(int i=1;i<=r;++i){
cin>>x;
if(cntl[x])cntl[x]--;
else cntr[x]++;
}
int lc=0,rc=0;
for(int i=1;i<=n;++i)
lc+=cntl[i],
rc+=cntr[i]; 
for(int i=1;i<=n;++i){
while(lc>rc&&cntl[i]>1)ans++,lc-=2,cntl[i]-=2;
while(rc>lc&&cntr[i]>1)ans++,rc-=2,cntr[i]-=2; 
}
cout<<ans+max(lc,rc)<<endl;
}
}

JAVAPhoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

import java.io.*;
import java.util.*;
import java.lang.*;
public class Main{
static InputReader sc;
static PrintWriter pw;
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
sc = new InputReader(inputStream);
pw = new PrintWriter(outputStream);
solve();
pw.close();
}
// static int L,R,top,bottom;
// static int cnt,edge;
// static long ans;
static boolean isIsland;
public static void solve() {
int t=sc.nextInt();
// int t=1;
u:while(t-->0){ 
int n=s(0);
int l=s(0);
int r=s(0);
int []left=new int [n+1];
int []right=new int [n+1];
for(int i=0;i<l;i++)
left[s(0)]++;
for(int i=0;i<r;i++)
right[s(0)]++;
long val;
for(int i=1;i<=n;i++){
val=Math.min(left[i],right[i]);
left[i]-=val;
right[i]-=val;
}
long ans=0l,cnt=0l;
// for(int i=1;i<=n;i++){
// ans+=(left[i]/2);
// left[i]%=2;
// ans+=(right[i]/2);
// right[i]%=2;
// }
long lT=0l,rT=0l;
for(int i=1;i<=n;i++){
lT+=left[i];
rT+=right[i];
}
val=Math.min(lT,rT);
ans+=val;
lT-=val;
rT-=val;
if(lT>0){
for(int i=1;i<=n;i++){
cnt+=left[i]/2;
}
if(2*cnt<lT){
ans+=lT-(2*cnt);
ans+=cnt;
}
else
ans+=lT/2;
}
else if(rT>0){
for(int i=1;i<=n;i++){
cnt+=right[i]/2;
}
if(2*cnt<rT){
ans+=rT-(2*cnt);
ans+=cnt;
}
else
ans+=rT/2;
}
pln(ans);
}
}
static void update_DAG(int cur,int val, int []graph, int n)
{
if(val>maxx[cur])
{
int x=graph[cur];
if(x!=-1)
update_DAG(x,val+1,graph,n);
maxx[cur]=val;
update(cur,val,n);
}
}
static int []bit, maxx;
static void update(int i,int val, int n)
{
while(i<=n)
{
bit[i]=Math.max(bit[i],val);
i=i+(i&(-i));
}
}
static int query(int i)
{
int ret=0;
while(i>0)
{
ret=Math.max(ret,bit[i]);
i=i-(i&(-i));
}
return ret;
} 
public static int [][]dir=new int [][]{{1,0},{0,1},{-1,0},{0,-1}}; 
public static int find(List<Integer> list, int x){
int l=0,r=list.size()-1,m;
while(l<=r){
m=(r-l)/2+l;
if(list.get(m)<=x)
l=m+1;
else
r=m-1;
}
return r;
} 
static class Node{
int val;
long cost;
Node next;
Node(int v,long c){
val=v;
next=null;
cost=c;
}
} 
public static long sum(long n){
long val=0l;
while(n>0){
val+=n%10;
n/=10;
}
return val;
}
// static class Node{
// int left,right;
// Node prev,next;
// Node(int i, int v){
// left=i;
// right=v;
// prev=next=null;
// }
// void remove(){
// this.prev.next=this.next;
// this.next.prev=this.prev;
// }
// void insert(Node node){
// node.next=this;
// node.prev=this.prev;
// node.prev.next=node;
// this.prev=node;
// }
// } 
public static int findDiameter(int r, List<List<Integer>>list){
return findFarthest(findFarthest(r,list)[0],list)[1];
}
public static int[] findFarthest(int u, List<List<Integer>>list){
int n=list.size();
boolean []vis=new boolean[n+1];
Queue<Integer>q=new LinkedList<>();
q.offer(u);
vis[u]=true;
int s,pr,cnt=0;
int []ar=new int[]{u,0};
while(q.size()>0){
s=q.size();
while(s-->0){
pr=q.poll();
if(ar[1]<cnt){
ar[1]=cnt;
ar[0]=pr;
}
for(int i:list.get(pr)){
if(!vis[i]){
vis[i]=true;
q.offer(i);
}
}
}
cnt++;
}
return ar;
}
public static long atMostK(char []chrr, int k){
if(k<0)
return 0;
int l=0,cnt=0;
long ans=0l;
for(int i=0;i<chrr.length;i++){
if(chrr[i]=='1')
cnt++;
while(cnt>k){
if(chrr[l++]=='1')
cnt--;
}
ans+=(long)(i-l)+1l;
}
return ans;
}
public static int ask(int l){
System.out.println(l);
System.out.flush();
return sc.nextInt();
}
public static void sort(int []arr){
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<arr.length;i++)
list.add(arr[i]);
Collections.sort(list);
for(int i=0;i<arr.length;i++)
arr[i]=list.get(i);
}
public static void sort(long []arr){
ArrayList<Long> list=new ArrayList<>();
for(int i=0;i<arr.length;i++)
list.add(arr[i]);
Collections.sort(list);
for(int i=0;i<arr.length;i++)
arr[i]=list.get(i);
}
public static void swap(char []chrr, int i, int j){
char temp=chrr[i];
chrr[i]=chrr[j];
chrr[j]=temp;
}
public static int countSetBits(long n){
int a=0;
while(n>0){
a+=(n&1);
n>>=1;
}
return a;
}
static class Pair{
int v,w;
Pair(int W, int V){
v=V;
w=W;
}
//*
}
/*/
public int compareTo(Pair p){
return (b-p.b);
}
public int hashCode(){
int hashcode = (a+" "+b).hashCode();
return hashcode;
}
public boolean equals(Object obj){
if (obj instanceof Pair) {
Pair p = (Pair) obj;
return (p.a==this.a && p.b == this.b);
}
return false;
}
}
//*/
static boolean isPrime(long n) { 
if (n <= 1) 
return false; 
if (n <= 3) 
return true; 
if (n % 2 == 0 || n % 3 == 0) 
return false; 
for (int i = 5; i * i <= n; i = i + 6) 
if (n % i == 0 || n % (i + 2) == 0) 
return false; 
return true; 
} 
static long gcd(long a, long b) { 
if (b == 0) 
return a; 
return a>b?gcd(b, a % b):gcd(a, b % a); 
} 
static long fast_pow(long base,long n,long M){
if(n==0)
return 1;
if(n==1)
return base;
long halfn=fast_pow(base,n/2,M);
if(n%2==0)
return ( halfn * halfn ) % M;
else
return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
static long modInverse(long n,long M){
return fast_pow(n,M-2,M);
}
public static int s(int n){
return sc.nextInt();
}
public static long s(long n){
return sc.nextLong();
}
public static String s(String n){
return sc.next();
}
public static double s(double n){
return sc.nextDouble();
}
public static void p(int n){
pw.print(n);
}
public static void p(long n){
pw.print(n);
}
public static void p(String n){
pw.print(n);
}
public static void p(double n){
pw.print(n);
}
public static void pln(int n){
pw.println(n);
}
public static void pln(long n){
pw.println(n);
}
public static void pln(String n){
pw.println(n);
}
public static void pln(double n){
pw.println(n);
}
public static void feedArr(long []arr){
for(int i=0;i<arr.length;i++)
arr[i]=sc.nextLong();
}
public static void feedArr(double []arr){
for(int i=0;i<arr.length;i++)
arr[i]=sc.nextDouble();
}
public static void feedArr(int []arr){
for(int i=0;i<arr.length;i++)
arr[i]=sc.nextInt();
}
public static void feedArr(String []arr){
for(int i=0;i<arr.length;i++)
arr[i]=sc.next();
}
public static String printArr(int []arr){
StringBuilder sbr=new StringBuilder();
for(int i:arr)
sbr.append(i+" ");
return sbr.toString();
}
public static String printArr(long []arr){
StringBuilder sbr=new StringBuilder();
for(long i:arr)
sbr.append(i+" ");
return sbr.toString();
}
public static String printArr(String []arr){
StringBuilder sbr=new StringBuilder();
for(String i:arr)
sbr.append(i+" ");
return sbr.toString();
}
public static String printArr(double []arr){
StringBuilder sbr=new StringBuilder();
for(double i:arr)
sbr.append(i+" ");
return sbr.toString();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}

DELPHI Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

const eps=1e-14;
besk=20000000000000{00000}; label 55,5,4,1,3,2,44,22;
type
mas=array[-20000..1704060+1] of int64;
integer=longint; zap=record p1,p2,p3:int64; end;
zap1=^zap;
var poss,mm,tip,ppos1,oldtt,ps,pos1,pos2,pred,color,buk,cur,init,res,oldpos,i1,j1,mask,stepp,n2,i,j,k,l,step,k1,mesto:longint;
sss:array[-1..1000] of string;
ss4,oldss,smin,ss3,ss,ss1,ss2:string;
newaans,aans:zap;
ddist,ott,tttt:extended;
pqqq:zap;
otal,al1,al2,acc, disk,prop,bet,al:extended; fl1,fl2,fl:boolean;
dr3,dr1,dr2,pt,ott1,ott2:zap;
pos,time,ost,zz,x:array[-1000..2100000] of int64;
stroka,sss1,sss2:array[-10..1200000] of char;
v3,v1,v2,pointx,pointy,vel,tt0,radius,ote,ddl,dl1,dl2:extended;
dd1,ddpos:array[-2..14,-200..65400] of int64;
kolpotom,pospotom,posy,zx,zy,z,kol,xxx,yyy,invfact,y,ansx,ansy,ugol,xx,yy:array[-1000..1100000] of int64;
mright,pol,dx,dy:array[-100..1850000] of int64;
p,posit,mnog,ii,jj,ttt,delta,tt1,tt2,sum,left,right,koll,newt,osn,oldot,num,oldt,ll,rr,znmax,aa,ot,t11,t01,t10,t00,opld,nap,t4,kk,dl,iii,jjj,aaa,bbb,ccc,bb,p0,t,xmax,xmin,ymax,ymin,newpos,newdl,len,pp3,ans1,ans2,modul,t0,t1,t2,dloch,koldel,mmax,stepen,pq,pp1,pp2,period, dolg,ot1,ot2,oldgr,predsum,pmin,tmin,kool,number,imin,qq,n,m,numpos,vx,vy,down,imax,t3,qq1,qq2,q1,q2,w,p3,p4,pmax,pmax2,p1,p2,hh,pos0,pp,maxot,tmax,nn,n1,q:int64; flag1:boolean;
b1,a1,b,c,a,zzz,fact,stan,a2,invx,invy,place,str,b2,z1,sum1,sum0,d0,d1,d:mas; flag2,flag:boolean; pl:longint;
kkol,i2,j2,ans,tt,sdvig,start,finish,izb, oldmax,newmax,posmax,zapas,razn,oldll,oldrr,ppp,minx,miny,maxx,maxy,kolplus,kolminus,razr,jmax,gr,grr,ener,dob,cc,ugg,r,ug:int64;
prost,zzan,zann:array[-10..2001001] of boolean;
newzan,zan:array[-1000000..1000000] of boolean;
zanx,marked:array[-1000000..1100000] of boolean;
path,dd,ddnew,dleft,dnomer:array[-1..521,-1..521,0..21] of int64;
ochh,newochh:array[0..1000000] of longint;
first,last,kolnenul,next1,next0,prev1,prev0,newoch,d2,och,lx,a3,b3,predok:array[-20000..1500000] of int64;
ddsum,ddd:array[-400..265200,-1..10] of int64;
gor,ver,polesum,sumgor,pole,newpole:array[-100..1300,-100..2300] of int64;
ssan,ssans,bufer:array[-1000..1000000] of char;
cosa,sina,cosb,sinb,rx,ry,px,py,h1,h2,h,l1,l2,otmax,v:int64;
obmen,ch:char;
mmat:array[0..200001,0..9,0..9] of int64;
flagg,fflag,ok,flagg1:boolean;
koled,oldx,oldy,numx,numy,xleft,xright,s,newplace,newstr,next,prev,aold:array[-1000..1200002] of int64;
function srav(i,j:longint):boolean; label 44;
begin
if (a[i]<a[j]) then begin srav:=true; goto 44; end;
if a[i]>a[j] then begin srav:=false; goto 44; end;
if a[i]=a[j] then if a1[i]<a1[j] then srav:=true else srav:=false;
if (a[i]=a[j])and(a1[i]=a1[j]) then if a2[i]<a2[j] then srav:=true else srav:=false;
44:
end;

procedure sl (k,l,m:integer); {k- dlina, l,m - nachalo dvuh blokov}
begin
i:=l;j:=m; flag:=true; step:=0;while flag do begin
if (srav(i,j)) then begin begin b[l+step]:=a[i];b1[l+step]:=a1[i];b2[l+step]:=a2[i];b3[l+step]:=a3[i];end;
inc(step);inc(i);
{writeln('step=',step,' i=',i);} end;
if (not srav(i,j)) then begin begin b[l+step]:=a[j];b1[l+step]:=a1[j];b2[l+step]:=a2[j];b3[l+step]:=a3[j];end;
inc(step);inc(j);end;
if ((i>=l+k) or (j>=m+k)) then flag:=false;
end;
if(i>=l+k) then repeat b[l+step]:=a[j];b1[l+step]:=a1[j];b2[l+step]:=a2[j]; b3[l+step]:=a3[j];
inc(step);inc(j);until (j>=m+k);
if(j>=m+k) then repeat b[l+step]:=a[i];b1[l+step]:=a1[i];b2[l+step]:=a2[i]; b3[l+step]:=a3[i];inc(step);inc(i);until (i>=l+k);
end;

procedure sort(var c:mas);
begin
k:=1; repeat
l:=1;m:=k+l; repeat sl(k,l,m); l:=l+2*k;m:=m+2*k; until (l>=n); k:=k*2; { writeln('dl bloka= ',k); }
for i:=1 to n do begin a[i]:=b[i];a1[i]:=b1[i];a2[i]:=b2[i];a3[i]:=b3[i]; end;
until (k>=n);
end;

function min (a,b:int64):int64;begin min:=b;if a<b then min:=a; end;
function max (a,b:int64):int64; begin max:=b;if a>b then max:=a; end;
function evkl(a,b:int64):zap1; var d,x,y,r,q,i,j,k,x1,x2,y1,y2:int64;
tt:zap; tt1:zap1; fl:boolean;
begin
fl:=false;
if a<b then begin r:=a;a:=b;b:=r; fl:=true; end;
x2:=1;x1:=0;y2:=0;y1:=1;
while b>0 do
begin q:=a div b; r:=a mod b; x:=x2-q*x1;y:=y2-q*y1;
a:=b;b:=r;x2:=x1;x1:=x;y2:=y1;y1:=y;
end;
if not fl then begin d:=a; x:=x2;y:=y2; tt.p1:=d;tt.p2:=x;tt.p3:=y; tt1:[email protected]; end else
begin d:=a; x:=x2;y:=y2; tt.p1:=d;tt.p2:=y;tt.p3:=x; tt1:[email protected]; end;
evkl:=tt1;
end;
function phi(a,b:double):double; label 222;var p:double;
begin
if (a>0)and (b>=0) then begin p:=arctan(b/a);goto 222; end;
if (a<0) then begin p:=pi+arctan(b/a);goto 222; end;
if (a>0)and (b<0) then begin p:=2*pi+arctan(b/a);goto 222; end;
if (a=0)and (b>0) then begin p:=pi/2;goto 222; end;
if (a=0)and (b<0) then begin p:=3*pi/2;goto 222; end;
222: phi:=p;
end;

function nod(a,b:int64):int64; var p,t:int64;
begin
a:=abs(a); b:=abs(b);
if (a>0)and(b>0) then
begin while (b>0) do begin t:=a mod b;a:=b;b:=t; end;
p:=a;
end else if a=0 then p:=b else p:=a;
nod:=p;
end;

function arccos(tt:extended):extended;
begin
if abs(tt)>1-1e-13 then
if tt>0 then arccos:=0 else arccos:=pi;
if tt=0 then arccos:=pi/2 else
if abs(tt)<=1-1e-13 then if tt>=0 then arccos:=arctan(sqrt(1-tt*tt)/tt)
else arccos:=pi+arctan(sqrt(1-tt*tt)/tt);
end;

function degg(a,k,modul:int64):int64; var p:int64; label 4;
begin
if k<=0 then degg:=1
else if odd(k) then degg:=(degg(a,k-1,modul)*a) mod modul else
begin p:=degg(a,k div 2,modul); degg:=(p*p) mod modul; end;
end;

function zaprmax(left,right:longint):int64;
begin
if left>=right then zaprmax:=y[left] else
begin
if not odd(left) and odd(right) then zaprmax:=zaprmax(left shr 1,right shr 1) else
begin
if odd(left) then zaprmax:=max(zaprmax(left+1,right),y[left]);
if not odd(right) then zaprmax:=max(zaprmax(left,right-1),y[right]);
end;
end;
end;




procedure udal(ii:longint);
begin next[prev[ii]]:=next[ii];prev[next[ii]]:=prev[ii]; end;





function pprost(pp:int64):boolean;
var i,j,t:longint; tt:extended; fl:boolean;
begin
tt:=pp;
tt:=sqrt(tt);
fl:=true;
for i:=2 to round(tt) do if pp mod i=0 then fl:=false;
pprost:=fl;
end;

function gl(c:char):boolean;
begin
if (c='a')or (c='o')or(c='e')or(c='i')or(c='u') then gl:=true else gl:=false;
end;
{ function slog(d1,d2:zap):zap1;
var t,tt,p,q:int64; ans:zap;
begin
p:=d1.x*d2.y+d1.y*d2.x;
q:=d1.y*d2.y;
t:=nod(p,q);
p:=p div t; q:=q div t;
ans.x:=p mod modul;ans.y:=q mod modul;
slog:[email protected];
end;

function umn(d1,d2:zap):zap1;
var t,tt,p,q:int64; ans:zap;
begin
p:=d1.x*d2.x;
q:=d1.y*d2.y;
t:=nod(p,q);
p:=p div t; q:=q div t;
ans.x:=p mod modul;ans.y:=q mod modul;
umn:[email protected];
end;

function sravfr(d1,d2:zap):boolean;
begin
if d1.x*d2.y<d2.x*d1.y then sravfr:=true else sravfr:=false;
end;
}
function bincoef(ii,jj:longint):int64;
var t1,t2,t3,p1,p2,p3,ot:int64;
begin
if ii>=jj then
begin
p1:=fact[ii];
p2:=fact[jj];
p3:=fact[ii-jj];
t2:=degg(p2,modul-2,modul);
t3:=degg(p3,modul-2,modul);
ot:=((p1*t2) mod modul*t3) mod modul;
bincoef:=ot;
end else bincoef:=0;
end;

function bincoef1(ii,jj:longint):int64;
var t1,t2,t3,p1,p2,p3,ot:int64;
begin
if ii>=jj then
begin
p1:=fact[ii];
p2:=invfact[jj];
p3:=invfact[ii-jj];
ot:=((p1*p2) mod modul*p3) mod modul;
bincoef1:=ot;
end else bincoef1:=0;
end;

procedure pech;
var j,i:longint;
begin
for i:=1 to p do begin for j:=1 to p do if zan[i] then write('*') else write('.'); writeln; end;
writeln;
{writeln('ot= ',ot); }
end;




begin

{ assign (input,'D:\Projects\input.txt');reset(input);
assign (output,'D:\Projects\output.txt'); rewrite(output);
}

readln(qq);
for stepp:=1 to qq do
begin
readln(p,aa,bb);
for i:=1 to p do begin read(a[i]); end;
for i:=1 to p do begin x[i]:=0; y[i]:=0; end;
for i:=1 to aa do inc(x[a[i]]);
for i:=aa+1 to p do inc(y[a[i]]);
cc:=abs(aa-bb) shr 1;
if bb>aa then for i:=1 to p do begin t:=x[i]; x[i]:=y[i]; y[i]:=t; end;
for i:=1 to p do z[i]:=min(x[i],y[i]);
for i:=1 to p do begin xx[i]:=xx[i-1]+x[i]; yy[i]:=yy[i-1]+y[i]; zz[i]:=zz[i-1]+z[i]; end;
ot:=0;
{ for i:=1 to p do write(x[i],' '); writeln;
for i:=1 to p do write(y[i],' '); writeln;

writeln('----------------');
}
tt:=0;
for i:=1 to p do if (x[i]>y[i])and(tt<cc) then
begin
razn:=min((x[i]-y[i]) shr 1,cc-tt);
ot:=ot+razn;
x[i]:=x[i]-razn;
y[i]:=y[i]+razn;
tt:=tt+razn;
end;

{ for i:=1 to p do write(x[i],' '); writeln;
for i:=1 to p do write(y[i],' '); writeln;
} p1:=0;
p2:=0;
for i:=1 to p do begin p1:=p1+x[i]; p2:=p2+y[i]; end;
cc:=abs(p2-p1) shr 1;
tt:=0;
for i:=1 to p do if (x[i]>y[i])and(tt<cc) then
begin
inc(tt); inc(ot);
dec(x[i]);
inc(y[i]);

end;

{ for i:=1 to p do write(x[i],' '); writeln;
for i:=1 to p do write(y[i],' '); writeln;


writeln;
} pp:=0;
for i:=1 to p do pp:=pp+abs(x[i]-y[i]);
{ ot:=ot+abs(aa-bb);
}
writeln(ot+pp shr 1);




{ writeln; }
end;







1: close (output);

end.


.NET Core C# Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces Phoenix and Socks solution codeforces

using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

namespace Hacking
{
#if ONLINE_JUDGE

#else
//using Library;
#endif

public class Algo
{
private StreamWriter _w;
private StreamReader _r;

public Algo(StreamReader r, StreamWriter w)
{
_w = w;
_r = r;
}

public void Run()
{
int t = _r.I();

for (int i = 1; i <= t; i++)
{
Solve();
}
}

private void Solve()
{
int n = _r.I();
int l = _r.I();
int r = _r.I();

int zl = 0;
int pl = 0, pr = 0;

int[] cc = _r.II(n);

HashSet<int> colors = new HashSet<int>(cc);

Dictionary<int, int> ll = new Dictionary<int, int>();
Dictionary<int, int> rr = new Dictionary<int, int>();

for (int i = 0; i < l; i++)
{
Increase(ll, cc[i]);
}
for (int i = l; i < n; i++)
{
Increase(rr, cc[i]);
}

foreach (int color in colors)
{
ll.TryGetValue(color, out int lc);
rr.TryGetValue(color, out int rc);

int both = Math.Min(lc, rc);
if (both > 0)
{
Decrease(ll, color, both);
Decrease(rr, color, both);
lc -= both;
rc -= both;
}

// remember pairs
if (lc > 0)
{
pl += lc / 2;
}
else if (rc > 0)
{
pr += rc / 2;
}
}

int tl = ll.Values.Sum();
int tr = rr.Values.Sum();

// switch paired - no need to recolour!
if (tr > tl)
{
int same = Math.Min((tr - tl) / 2, pr);
tr -= same * 2;

// pay for switch
zl += same;
}
else if (tl > tr)
{
int same = Math.Min((tl - tr) / 2, pl);
tl -= same * 2;

// pay for switch
zl += same;
}

// rest are switch + repaint
int diff = Math.Abs(tl - tr) / 2;
zl += diff;

// repaint
int repaint = (tl + tr) / 2;
zl += repaint;

_w.WriteLine(zl);
}

void Increase<T>(IDictionary<T, int> dic, T key)
{
dic.TryGetValue(key, out int value);
dic[key] = value + 1;
}

void Decrease<T>(IDictionary<T, int> dic, T key, int count = 1)
{
dic.TryGetValue(key, out int value);

int newValue = value - count;
if (newValue < 0)
throw new InvalidOperationException();
if (newValue == 0)
dic.Remove(key);
else
dic[key] = value - count;
}
}


public static class Program
{
public static void Main(string[] args)
{
#if !ONLINE_JUDGE
string input = @"4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3";
string expectedOutput = @"2
3
5
3";
#endif

var f = new Factory();
#if !ONLINE_JUDGE
f.InputContent = input;
#endif

var r = f.GetReader();
var w = f.GetWriter();
Algo p = new Algo(r, w);
p.Run();
w.Flush();

#if !ONLINE_JUDGE
string result = f.GetOutputContent();
var resultLines = result.Split(new[] { "\r", "\n" }, StringSplitOptions.RemoveEmptyEntries);
var expectedLines = expectedOutput.Split(new[] { "\r", "\n" }, StringSplitOptions.RemoveEmptyEntries);

for (int i = 0; i < expectedLines.Length; i++)
{
if (!string.Equals(expectedLines[i].Trim(), resultLines[i].Trim()))
{
throw new InvalidOperationException($"Line {i + 1}: expected \"{expectedLines[i]}\", was \"{resultLines[i]}\".");
}
}
#endif
}
}

public static class ReaderExtensions
{
static char[] tokens = new char[4];

public static ReadOnlySpan<char> NextToken(this StreamReader sr)
{
int size = 0;

bool skipWhiteSpaceMode = true;
while (true)
{
int nextChar = sr.Read();
if (nextChar == -1)
{
break;
}

char ch = (char)nextChar;
if (char.IsWhiteSpace(ch))
{
if (!skipWhiteSpaceMode)
{
if (ch == '\r' && (Environment.NewLine == "\r\n"))
{
sr.Read();
}
break;
}
}
else
{
skipWhiteSpaceMode = false;
if (size == tokens.Length)
{
char[] a2 = new char[tokens.Length * 2];
Array.Copy(tokens, a2, tokens.Length);
tokens = a2;
}
tokens[size++] = ch;
}
}

return new ReadOnlySpan<char>(tokens, 0, size);
}

public static char C(this StreamReader sr)
{
while (true)
{
int nextChar = sr.Read();
if (nextChar == -1)
{
// End of stream reached
return (char)0;
}

char ch = (char)nextChar;
if (!char.IsWhiteSpace(ch))
{
return ch;
}
}
}

public static int I(this StreamReader sr)
{
var token = new string(NextToken(sr));
return int.Parse(token);
}

public static double D(this StreamReader sr, bool acceptAnyDecimalSeparator = true)
{
var token = NextToken(sr);
if (acceptAnyDecimalSeparator)
{
var tokens = new string(token).Replace(',', '.');
double result = double.Parse(tokens, CultureInfo.InvariantCulture);
return result;
}
else
{
double result = double.Parse(token);
return result;
}
}

public static decimal M(this StreamReader sr, bool acceptAnyDecimalSeparator = true)
{
var token = NextToken(sr);
if (acceptAnyDecimalSeparator)
{
var tokens = new string(token).Replace(',', '.');
decimal result = decimal.Parse(tokens, CultureInfo.InvariantCulture);
return result;
}
else
{
decimal result = decimal.Parse(token);
return result;
}
}

public static int[] II(this StreamReader r, int n)
{
int[] ret = new int[n];
for (int i = 0; i < n; i++)
ret[i] = r.I();

return ret;
}

public static short[] Digits(this StreamReader r, int n)
{
short[] ret = new short[n];
for (int i = 0; i < n; i++)
ret[i] = (short)(r.C() - (int)'0');

return ret;
}

public static bool[] BB(this StreamReader r, int n)
{
bool[] ret = new bool[n];
for (int i = 0; i < n; i++)
ret[i] = r.C() == '1';

return ret;
}

public static bool[] PlusesMinuses(this StreamReader r, int length)
{
bool[] ret = new bool[length];
for (int i = 0; i < length; i++)
ret[i] = r.C() == '+';

return ret;
}

public static Int16[] SS(this StreamReader r, int n)
{
Int16[] ret = new Int16[n];
for (int i = 0; i < n; i++)
ret[i] = Int16.Parse(r.NextToken());

return ret;
}

public static long[] LL(this StreamReader r, int n)
{
long[] ret = new long[n];
for (long i = 0; i < n; i++)
ret[i] = long.Parse(r.NextToken());

return ret;
}

public static void WriteLine(this StreamWriter w, int i)
{
w.WriteLine(i.ToString());
}

public static void WriteLine(this StreamWriter w, char[] z)
{
w.WriteLine(new string(z));
}

public static void WriteYESNOLine(this StreamWriter w, bool b)
{
w.WriteLine(b ? "YES" : "NO");
}

public static void WriteNums(this StreamWriter w, IEnumerable<int> nn)
{
bool first = true;
foreach (int n in nn)
{
if (first)
{
first = false;
}
else
{
w.Write(' ');
}
w.Write(n);
}
w.WriteLine();
}

public static void WriteNums(this StreamWriter w, IEnumerable<long> nn)
{
bool first = true;
foreach (long n in nn)
{
if (first)
{
first = false;
}
else
{
w.Write(' ');
}
w.Write(n);
}
w.WriteLine();
}
}

public class Factory
{
private StreamWriter _sw;
private StreamReader _sr;
#if !ONLINE_JUDGE
public string InputContent { get; set; }
private MemoryStream _ms;

public string GetOutputContent()
{
return Encoding.ASCII.GetString(_ms.ToArray());
}
#endif

public StreamWriter GetWriter()
{
return _sw = _sw ?? new StreamWriter(GetOutputStream());
}

Stream GetOutputStream()
{
#if ONLINE_JUDGE
return Console.OpenStandardOutput();
#else
return _ms = new MemoryStream();
#endif
}

public StreamReader GetReader()
{
return _sr = _sr ?? new StreamReader(GetInputStream());
}

Stream GetInputStream()
{
#if ONLINE_JUDGE
return Console.OpenStandardInput();
#else
// return File.OpenRead(@"C:\dev\ConsoleApp1\ConsoleApp1\bin\Debug\input.txt");

return new MemoryStream(Encoding.ASCII.GetBytes(InputContent), false);
#endif
}

public void Dispose()
{
_sw?.Dispose();
_sr?.Dispose();
}
}
}

 

Phoenix and Socks solution codeforces Splitting a String Into Descending Consecutive Values Minimum Adjacent Swaps to Reach the Kth Smallest Number Minimum Interval to Include Each Query
 
 

Leave a Comment