Zad E
Wzorcówka

Pierwsze rozwiązanie tego zadania, dalece nie to najprostsze - ktoś wie, dlaczego to działa?

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
  int TT,n,i,j,sum,A[100000],B[100000],p,q,r;
  scanf("%d",&TT);
  while(TT--)
  {
    scanf("%d",&n);
    for(i=0; i<n; i++)
      scanf("%d",&A[i]);
    for(i=0; i<n; i++)
      scanf("%d",&B[i]);
    sort(A,A+n);
    sort(B,B+n);
    p = 1;
    q = n;
    while(p<q)
    {
      r = (p+q+1)/2;
      int lev = -1;
      bool ok = true;
      for(i=0; i<r; i++)
      {
        if (A[n-r+i]<B[i])
      ok = false;
    if (A[n-r+i]==B[i])
    {
      if (lev==-1)
        lev = B[i];
      else
        ok = (B[i]==lev);
    }
      }
      if (ok)
        p = r;
      else
        q = r-1;
    }
    sum = -200*n;
    for(i=0; i<p; i++)
    {
      if (B[i]<A[n-p+i])
        sum+=400;
      if (B[i]==A[n-p+i])
        sum+=200;
    }    
    printf("%d\n",sum);
  }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License