Thanks LLI! By the way, I used integer modular arithmetic in the first place, and still got WA 20 after rejudge.

After some debugging I realize I checked the linear independency incorrectly (in particular, I did the row echelon form wrongly). Here is the test case helped me find out the bug:

Input:
5 4
1 2 3 4
2 4 5 9
3 6 7 1
1 1 1 9
3 2 1 9
1
2
3
4
5

Expected output:
10
1
2
3
4

When will new contests be added as well?

Consider a failing scenario which is like

3 2
1 0 0
0 1 0
1 1 0
1
2
3

try test:
11 10
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
1
1
1
1
1
1
1
1
1
1
1

Out:
10
1
2
3
4
5
6
7
8
9
10

Edited by author 17.07.2010 23:05

You can use gauss over prime modular ring instead of long arithmetics
Just select lucky module =)

You can use Gram-Schmidt process for checking linear independency and try 1999.

Yes, "lexicographic" has its usual meaning.

The trouble really can be in preсision.
If you use simple Gauss with type "long double" you'll always get WA.
Do calculations in long integer numbers or modulo big prime number.
If you want, i can send you some my solutions, WA 9, WA 17, AC.

Output 0 if number of vectors purchased is <n

You've described very scary way of solving this problem (with 0-vectors and reverse values) =)
All you need to do in this problem is Gaussian elimination. Well-realized by some large modulo, it'll give you right answers with high probability and without any precalculations and 0-vectors checkings (by the way, I don't understand why giving 0-vectors is incorrect if not forbidden by the problem statement?)

Well you can use a kind of gaussian elimination mod P with a prime P not very big ( to avoid TLE ). Thanks to Minilek. gl! Eric.



Edited by author 14.04.2008 23:52

program ex;

const
  maxn=2000;
  maxm=50;
  zero=1e-15;

var
  g: Array[0..maxn, 1..maxm] of extended;
  cost: Array[1..maxn] of longint;
  from: Array[1..maxn] of longint;
  n, m: longint;
  ans: longint;
  num: Array[1..maxm] of longint;
  tot: longint;
  kk: Array[1..maxn] of longint;

procedure init;
var
  i, j: longint;
begin
  read(n, m);
  for i:=1 to n do
    for j:=1 to m do
      read(g[i, j]);
  for i:=1 to n do begin
    read(cost[i]);
    from[i]:=i;
  end;
end;

procedure qsort(l, r: longint);
var
  i, j: longint;
  x, y: longint;
  t: longint;
begin
  i:=l;
  j:=r;
  x:=cost[(l+r) shr 1];
  y:=from[(l+r) shr 1];
  while i<=j do begin
    while (cost[i]<x)or(cost[i]=x)and(from[i]<y) do inc(i);
    while (cost[j]>x)or(cost[j]=x)and(from[j]>y) do dec(j);
    if i<=j then begin
      g[0]:=g[i];
      g[i]:=g[j];
      g[j]:=g[0];
      t:=cost[i];
      cost[i]:=cost[j];
      cost[j]:=t;
      t:=from[i];
      from[i]:=from[j];
      from[j]:=t;
      inc(i);
      dec(j);
    end;
  end;
  if j>l then qsort(l, j);
  if i<r then qsort(i, t);
end;

function can(x: longint): boolean;
var
  i, j: longint;
  len1, len2: extended;
  sum: extended;
  co: extended;
  tt: extended;
  temp: Array[1..maxn] of extended;
begin
  for i:=1 to tot do begin
    sum:=0;
    len1:=0;
    len2:=0;
    for j:=1 to m do begin
      sum:=sum+g[x, j]*g[i, j];
      len1:=len1+g[x, j]*g[x, j];
      len2:=len2+g[kk[i], j]*g[kk[i], j];
    end;
    len1:=sqrt(len1);
    len2:=sqrt(len2);
    if abs(len1)<=zero then
      exit(false);
    co:=sum/len1/len2;
    tt:=len1*co;
    for j:=1 to m do
      temp[j]:=g[kk[i], j]*tt/len2;
    for j:=1 to m do
      g[x, j]:=g[x, j]-temp[j];
  end;
  for j:=1 to m do
    if abs(g[x, j])>zero then
      exit(true);
  exit(false);
end;

procedure solve;
var
  i: longint;
begin
  qsort(1, n);
  tot:=1;
  num[1]:=from[1];
  ans:=ans+cost[1];
  kk[1]:=1;
  for i:=2 to n do
    if can(i) then begin
      inc(tot);
      kk[tot]:=i;
      num[tot]:=from[i];
      ans:=ans+cost[i];
      if tot=m then
        exit;
    end;
end;

procedure print;
var
  i, j: longint;
  t: longint;
begin
  if tot<m then
    writeln(0)
  else begin
    writeln(ans);
    for i:=1 to m do
      for j:=i+1 to m do
        if num[i]>num[j] then begin
          t:=num[i];
          num[i]:=num[j];
          num[j]:=t;
        end;
    for i:=1 to m do
      writeln(num[i]);
  end;
end;

begin
  init;
  solve;
  print;
end.

n = 2
i = d = 0
j = 1

a:
1 1
1 1

First result:
1 1
0 0

Second result:
1 1
0 1

I've got AC. The tests are very difficult. REMEMBER: The epsilon should be very small!!!