Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Such a simple problem,Why WA?

Posted by kenin at 2006-10-27 20:25:52 on Problem 3018
#include <cstdio>
#include <cstdlib>

const long MaxN=501;
const long MaxM=1000;

long N,M;
long box[MaxN][MaxM],du[MaxN],ans[MaxN];
bool way[MaxN][MaxN];

void Open() {
  freopen ("3018.in","r",stdin);
  freopen ("3018.out","w",stdout);     
}

void Close() {
  fclose(stdin);
  fclose(stdout);     
}

int comp(const void *a,const void *b) {
  return *(long *)a-*(long *)b;    
}

void init() {
  long i,j;
  N++;
  for (i=0;i<N;i++)
    for (j=0;j<M;j++) scanf ("%ld",&box[i][j]);
  for (i=0;i<N;i++) qsort(&box[i],M,sizeof(long),comp);
}

void work() {
  long i,j,l;
  bool ok=true;
  for (i=0;i<N;i++) for (j=0;j<N;j++) way[i][j]=false;
  for (i=0;i<N;i++) {ans[i]=0; du[i]=0;}
  for (i=0;i<N;i++) {
    if (du[i]<0) continue;
    for (j=1;j<N;j++) {
      if (i==j||du[j]<0) continue;
      for (l=0;l<M;l++) if (box[i][l]>=box[j][l]) break;
      if (l==M) {way[i][j]=true; du[j]++;}
      else if (i==0) du[j]=-1;
    }
  }
  while (ok) {
    ok=false;
    for (i=0;i<N;i++) {
      if (du[i]!=0) continue;
      for (j=0;j<N;j++) if (way[i][j]) {du[j]--; ans[j]=ans[i]+1; ok=true;}
      du[i]=-1;
    }
  }
}

void output() {
  long Mans=0,i;
  for (i=0;i<N;i++)
    if (ans[i]>Mans) Mans=ans[i];
  if (Mans==0) printf ("Please look for another gift shop!\n");
  else printf ("%ld\n",Mans);
}

int main() {
//  Open();
  while (scanf ("%ld%ld",&N,&M)!=EOF) {
    init();
    work();
    output();      
  }
//  Close();
  return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator