// Online adversary for bipartite matching - see Karp, Vazirani, & Vazirani
// BPW, 2/29/04

#include <stdio.h>

main()
{
int n,i,j,k,p,ones,moves,seed,peek;
int *boysMatchedADON,*boysMatchedALG;  // The two matchings
int *column,*seal;  // The current column and ADON's sealed moves
int boyALG;

printf("Enter n and seed\n");
scanf("%d %d",&n,&seed);
printf("Do you want to peek at sealed moves of online adversary? (0/1)\n");
scanf("%d",&peek);
if (peek)
  printf("Shame on you . . .\n");
else
  printf("Virtue will not go unrewarded . . .\n");
srandom(seed);
boysMatchedADON=(int*) malloc(n*sizeof(int));
boysMatchedALG=(int*) malloc(n*sizeof(int));
column=(int*) malloc(n*sizeof(int));
seal=(int*) malloc(n*sizeof(int));
if (!boysMatchedADON || !boysMatchedALG || !column || !seal)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}

for (i=0;i<n;i++)
  boysMatchedADON[i]=boysMatchedALG[i]=0;

for (i=0;i<n/2;i++)
{
  printf("Round %d\n",i+1);
  ones=0;  // Number of ones in column
  // Construct column
  for (j=0;j<n;j++)
    if (boysMatchedADON[j] || boysMatchedALG[j])
      column[j]=0;
    else
    {
      column[j]=1;
      ones++;
    }
  // Randomly choose a one to seal
  j=1+abs(random())%ones;
  p=(-1);
  for (k=0;k<j;k++)
    for (p++;
         !column[p];
         p++)
      ;
  seal[i]=p;
  if (peek)
    printf("PEEK at sealed %d\n",p);
  boysMatchedADON[p]=1;
  printf("Column is: ");
  for (j=0;j<n;j++)
    if (column[j])
      printf(" %d",j);
  printf("\n");
  while (1)
  {
    printf("Choose! (-1 to refuse)\n");
    // Note - ALG always has a move available
    scanf("%d",&boyALG);
    if (boyALG==(-1))
      break;
    if (boyALG>=0 && boyALG<n && column[boyALG])
      break;
  }
  if (boyALG!=(-1))
    boysMatchedALG[boyALG]=1;
}

for (i=n/2;i<n;i++)
{
  printf("Round %d\n",i+1);
  ones=0;  // Number of ones in column
  // Construct column
  for (j=0;j<n;j++)
    if (boysMatchedADON[j])
      column[j]=0;
    else
    {
      column[j]=1;
      ones++;
    }
  // Randomly choose a one to seal
  j=1+abs(random())%ones;
  p=(-1);
  for (k=0;k<j;k++)
    for (p++;
         !column[p];
         p++)
      ;
  seal[i]=p;
  if (peek)
    printf("PEEK at sealed %d\n",p);
  boysMatchedADON[p]=1;
  moves=0; // Number of moves available to ALG
  printf("Column is: ");
  for (j=0;j<n;j++)
    if (column[j])
      if (boysMatchedALG[j])
        printf(" (%d)",j);
      else
      {
        moves++;
        printf(" %d",j);
      }
  printf("\n");
  if (moves==0)
  {
    printf("No possible match for this column\n");
    continue;
  }
  while (1)
  {
    printf("Choose! (-1 to refuse)\n");
    scanf("%d",&boyALG);
    if (boyALG==(-1))
      break;
    if (boyALG>=0 && boyALG<n && column[boyALG] && !boysMatchedALG[boyALG])
      break;
  }
  if (boyALG!=(-1))
    boysMatchedALG[boyALG]=1;
}
printf("ADON's matching: ");
for (i=0;i<n;i++)
  printf(" %d",seal[i]);
printf("\n");
}