Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

raks8877's blog

By raks8877, history, 8 months ago, In English,
 
 
 
 

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by raks8877 (previous revision, new revision, compare).

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

c++ code

include<bits/stdc++.h>

using namespace std; typedef long long ll;

int BS (int ar[], int l, int r, int k)

{ int m = 0,pos = -1; while(l <= r) { m = l + (r-l)/2;

if(k > ar[m])
    {
        pos = m;
        l = m + 1;
    }
    else
    {
        r = m - 1;
    }
}
return pos+1;

}

int BSg (int ar[], int l, int r, int k)

{ int m = 0,pos = -1; while(l <= r) { m = l + (r-l)/2;

if(k >= ar[m])
    {
        pos = m;
        l = m + 1;
    }
    else
    {
        r = m - 1;
    }
}
return pos+1;

}

int main() { int n, m; cin >> n >> m; int ar1[n], ar2[m];

for(int i = 0; i < n; i++)
    cin >> ar1[i];
for(int i = 0; i < m; i++)
    cin >> ar2[i];

sort(ar1,ar1+n);
sort(ar2,ar2+m);

ll val1 = 0, val2 = 0;
for(int i = 0; i < n; i++)
{
    ll t1 = BS(ar2,0,m-1,ar1[i]);
    ll t2 = m - BSg(ar2,0,m-1,ar1[i]);
    val1 += (t1*t2);
}
for(int i = 0; i < m; i++)
{
    ll t1 = BS(ar1,0,n-1,ar2[i]);
    ll t2 = n - BSg(ar1,0,n-1,ar2[i]);
    //cout << t1 << " " << t2 << " " << n-t2-1 << " " << ar2[i] << endl;
    val2 += (t1*t2);
}

if(val1 > val2)
    cout << "Monk " << (val1-val2) << endl;
else if(val1 < val2)
    cout << "!Monk " << (val2-val1) << endl;
else
    cout << "Tie\n";

}

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

java code:

import java.util.*;

class TestClass {

static int BS(int ar[], int l, int r, int k)
{
    int m = 0 , pos = -1;
    while(l <= r)
    {
        m = l + (r-l)/2;
        if(k > ar[m])
        {
            pos = m;
            l = m + 1;
        }
        else
        {
            r = m &mdash; 1;
        }
    }
    return pos + 1;
}

static int BSg(int ar[], int l, int r, int k)
{
    int m = 0 , pos = -1;
    while(l <= r)
    {
        m = l + (r-l)/2;
        if(k >= ar[m])
        {
            pos = m;
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }
    return pos + 1;
}


public static void main(String args[] ) throws Exception {
    Scanner input = new Scanner(System.in);
    int n, m;
    n = input.nextInt();
    m = input.nextInt();
    int ar1[] = new int[n];
    int ar2[] = new int[m];

    for(int i = 0; i < n; i++)
        ar1[i] = input.nextInt();

    for(int i = 0; i < m; i++)
        ar2[i] = input.nextInt();

    long val1,val2;
    val1 = val2 = 0;
    Arrays.sort(ar1);
    Arrays.sort(ar2);

    for(int i = 0; i < n; i++)
    {
        long t1 = BS(ar2,0,m-1,ar1[i]);
        long t2 = m - BS(ar2,0,m-1,ar1[i]);
        //System.out.println(t1 + " " + t2 );
        val1 += (t1*t2);
    }

    for(int i = 0; i < m; i++)
    {
        long t1 = BS(ar1,0,n-1,ar2[i]);
        long t2 = n - BS(ar1,0,n-1,ar2[i]);
        //System.out.println(t1 + " " + t2 );
        val2 += (t1*t2);
    }

    if(val1 > val2)
        System.out.println("Monk " + (val1-val2));
    else if(val1 < val2)
        System.out.println("!Monk " + (val2-val1));
    else
        System.out.println("Tie");


}

}