bzoj1034: [ZJOI2008]泡泡堂BNB

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 100100;

int n, a[maxn], b[maxn];

int solve(int* a, int* b)
{
    // Self = a, while Opponent = b
    int l1 = 1, r1 = n, l2 = 1, r2 = n;
    int res = 0;
    while (l1 <= r1 && l2 <= r2) {
        if (a[l1] > b[l2]) {
            res += 2;
            l1++, l2++;
        } else if (a[r1] > b[r2]) {
            res += 2;
            r1--, r2--;
        } else {
            if (a[l1] == b[r2])
                res += 1;
            l1++, r2--;
        }
    }
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    int res1 = solve(a, b),
        res2 = 2 * n - solve(b, a);
    printf("%d %d\n", res1, res2);
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 200100;

struct per { int org, val; };

bool operator < (per a, per b) {
    return a.val < b.val;
}

int n, cnt[maxn], cntp;
per arr[maxn];

int get_final_val(int org)
{
    // Input the origin, and calculate the (earnings) of the 'org' team.
    // Scan from the people of the lowest scores
    memset(cnt, 0, sizeof(cnt));
    cntp = 0;
    // Processing distinct array. This array is only related to the participants'
    // relative position, and +1 represents one member on the self side, -1
    // represents one member on the other side, 0 represents no winners and so on.
    for (int i = 1; i <= 2 * n; i++) {
        if (arr[i].val != arr[i - 1].val)
            cntp++;
        if (arr[i].org == org)
            cnt[cntp]++;
        else
            cnt[cntp]--;
    }
    // Now we've done sorting out the cnt[] and cntp things...
    // We are about to calculate the values.
    // Suppose the example data is arranged in such a way:
    //     arr(self):     50    40    30 25 20 15    5 0
    //     arr(other): 55    45    35       20 15 10 5 0
    //     cnt[]:       +  +  -  +  -  +  +  x  x  - x x
    // (Whereas + represents cnt[] = +1, - represents cnt[] = -1, x represents cnt[] = 0)
    // When we work through the cnt[] array, we iterate from the smaller side.
    //     It is supposed, that when some time the sum reaches 0 (i.e. greater than 0),
    //     the addition that makes it overpass 0 should not be counted. This is
    //     obvious, because you may not win someone with a higher score than you.
    int tmpsum = 0;
    int res = 0;
    for (int i = 1; i <= cntp; i++) {
        int t = cnt[i];
        if (t <= 0) {
            tmpsum += t;
            continue;
        } else {
            // It should not exceed this value, as described before in the
            // documentation.
            if (tmpsum + t > 0) {
                // This overexceeding will not be patched by the same team after this
                res -= (tmpsum + t);
                t = -tmpsum;
            }
            res += t;
            tmpsum += t;
        }
    }
    return res + n;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // The power values of ZheJiang participants
    for (int i = 1; i <= n; i++) {
        arr[i].org = 1;
        scanf("%d", &arr[i].val);
    }
    // The power values of opponents'
    for (int i = 1; i <= n; i++) {
        arr[i + n].org = 2;
        scanf("%d", &arr[i + n].val);
    }
    // Begin brute-forcing when we need to sort
    sort(arr + 1, arr + 2 * n);
    // Now it's the real time to calculate with "work"
    printf("%d %d\n", get_final_val(1), 2 * n - get_final_val(2));
    return 0;
}

from pydatagen import *
n = randrange(2, 100000)
a = randlist(n, range(1, 10 ** 8))
b = randlist(n, range(1, 10 ** 8))
printf('%d\n' % n)
for i in a + b:
    printf('%d\n' % i)
fclose()