Skip to content

Instantly share code, notes, and snippets.

@zsrinivas
Created May 22, 2014 11:07
Show Gist options
  • Save zsrinivas/45b64aefd39fab947414 to your computer and use it in GitHub Desktop.
Save zsrinivas/45b64aefd39fab947414 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
inline int get_int()
{
int n=0;
char c=0;
while(c<33)
c=getchar_unlocked();
while(c>='0'&&c<='9')
{
n=(n<<3)+(n<<1)+(c-'0');
c=getchar_unlocked();
}
return n;
}
int main(int argc, char const *argv[])
{
int test,n,i;
int a[1000010];
long long int count,cinderella,girlwoman;
test=get_int();
while(test--)
{
n=get_int();
count=((n)*(n-1))/2;
for (i = 0; i < n; ++i)
a[i]=get_int();
girlwoman=0;
cinderella=0;
for (i = 0; i < n; ++i)
{
if (a[i]==2||a[i]==1)
{
girlwoman++;
}
else if (a[i]==0)
{
cinderella++;
}
}
count-=(girlwoman*(girlwoman-1))/2;
for (i = 0; i < n; ++i)
{
if (a[i]==0)
{
count-=n-i-1;
cinderella--;
}
else if (cinderella>0)
{
count-=cinderella;
}
}
printf("%lld\n",count);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment