152 WA, please help

[rickyliu]

This problem seems simple. However, my brute force solution got WA. As the problem does not say explicitly, I assume the input can be in real numbers. My algorithm is as follows:

1. initialize result[] to 0 and read in all trees
2. for each tree i, find the minimum distance amongst all other trees and store it in minDistance[i]
3. if minDistance[i] < 10, add 1 to the corresponding bin, ie, ++result[(int) minDistance[i]]
4. print out the result array

Did I miss something or misunderstand anything? Would anyone please provide a set of input/output for my testing - I can only find one in the forum and my program got it right. Here is my code:

Code: Select all

#include <cstdio>
#include <cmath>
#include <climits>
using namespace std;

#ifndef DBL_MAX
const double DBL_MAX = 1.7976931348623158e+308;
#endif

struct Point
{
  double x, y, z;
};

Point tree[5000];
int treeNum = 0;
int result[10] = {0};
double minDistance[5000];

int main()
{
  for (int i = 0; i < 5000; ++i) {
    minDistance[i] = DBL_MAX;
  }
  while (true) {
    Point & p = tree[treeNum];
    scanf("%lf %lf %lf", &p.x, &p.y, &p.z);
    if (p.x == 0 && p.y == 0 && p.z == 0) break;
    ++treeNum;
  }
  for (int i = 0; i < treeNum; ++i) {
    for (int j = 0; j < treeNum; ++j) {
      if (i == j) continue;
      double xDist = tree[j].x - tree[i].x;
      double yDist = tree[j].y - tree[i].y;
      double zDist = tree[j].z - tree[i].z;
      double distSquare = xDist * xDist + yDist * yDist + zDist * zDist;
      double dist = sqrt(distSquare);
      if (dist < minDistance[i]) {
        minDistance[i] = dist;
      }
    }
    if (minDistance[i] < 10) {
      ++result[(int) minDistance[i]];
    }
  }
  for (int i = 0; i < 10; ++i) {
    printf("%4d", result[i]);
  }
  putchar('\n');
}


[rickyliu]

I got AC but I did not feel happy. I managed to find the input and output of the judge used. I have verified this by just sending the output line and got AC. Then, I verified with my program's output and found no differences. Since my compiler (GCC 3.4.2 mingw-special) changed the variable treeNum to 0 after reading 5,000 input lines (it worked when I added -O2 to optimize the code - weird and possibly compiler's bug), I started to suspect this problem might be caused by the compiler used by the judge.

To verify my claim, I rewrote the above C++ program so that it could be compiled using a C compiler. I submitted this C program and got AC. Then, I submitted the same program but asked the judge to use C++ compiler. I got WA this time!

Could someone please explain to me why the results were different using different compilers? Here is the rewriting code:

Code: Select all

#include <stdio.h>
#include <math.h>
#include <limits.h>

#ifndef DBL_MAX
const double DBL_MAX = 1.7976931348623158e+308;
#endif

struct Point
{
  double x, y, z;
};

struct Point tree[5000];
int treeNum = 0;
int result[10] = {0};
double minDistance[5000];

int main()
{
  int i, j;
  double xDist, yDist, zDist, distSquare, dist;

  for (i = 0; i < 5000; ++i) {
    minDistance[i] = DBL_MAX;
  }
  while (1) {
    scanf("%lf %lf %lf", &tree[treeNum].x, &tree[treeNum].y, &tree[treeNum].z);
    if (tree[treeNum].x == 0 && tree[treeNum].y == 0 && tree[treeNum].z == 0) break;
    ++treeNum;
  }
  for (i = 0; i < treeNum; ++i) {
    for (j = 0; j < treeNum; ++j) {
      if (i == j) continue;
      xDist = tree[j].x - tree[i].x;
      yDist = tree[j].y - tree[i].y;
      zDist = tree[j].z - tree[i].z;
      distSquare = xDist * xDist + yDist * yDist + zDist * zDist;
      dist = sqrt(distSquare);
      if (dist < minDistance[i]) {
        minDistance[i] = dist;
      }
    }
    if (minDistance[i] < 10) {
      ++result[(int) minDistance[i]];
    }
  }
  for (i = 0; i < 10; ++i) {
    printf("%4d", result[i]);
  }
  putchar('\n');
  return 0;
}


[rickyliu]

Sorry that I made a very stupid mistake in my code.
SA, please delete this post. Thanks.

[mic122]

I renew this topic. I got Runtime Error. Could sb explain what I have wrong ?

Code: Select all

#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define rep(x,n) for (int x = 0; x < n; x++)
#define pb push_back
using namespace std;
struct tr
{
 double x,y,z;
};
struct cmp
{
 bool operator() (tr a, tr b)
 {
  if (a.x == b.x)
  {
    if (a.y == b.y)
    {
    if (a.z == b.z) return true; else return (a.z < b.z);
    }
    else return (a.y < b.y);
  } else return (a.x < b.x);

 }
};
set <tr,cmp> D;
int main()
{  tr a,b,d;
vector <int> zaj; zaj.resize(10,0);
 do
 {
  cin >> a.x >> a.y >> a.z;
 D.insert(a);
 } while (! (a.x == 0 && a.y == 0 && a.z == 0));
 D.erase(D.begin());
 for (set<tr,cmp>::iterator it = D.begin(); it != D.end(); it++)
 {
  double d1 = -1,d2 = -1; b = *(it);
 // cout <<"------------------ " <<b.x << " " << b.y << " "  <<b.z << "\n";
  if (it != D.begin())
  {
   --it; d = *(it); ++it;
   d1 = sqrt((b.x-d.x)*(b.x-d.x) + (b.y-d.y)*(b.y-d.y) + (b.z-d.z)*(b.z-d.z));
  // cout << "D1" <<d1 << "\n";
  }
  set<tr,cmp>::iterator itk = D.end(); itk--;
  if (it != itk)
  {
   ++it; d = *(it); --it;
   d2 = sqrt((b.x-d.x)*(b.x-d.x) + (b.y-d.y)*(b.y-d.y) + (b.z-d.z)*(b.z-d.z));
  // cout << "d2 " << d2 << "\n";
  }
  if (d1 != -1 && d2 != -1)
  {
//cout << "czc " << int(d1) << " " << int(d2) << "\n";
   int g = min(int(d1),int(d2)); if (g < 10)++zaj[g];
  // cout << "better " << "\n";
  }
  else if (d1 == -1 && d2 < 10) { ++zaj[int(d2)]; } else if (d1 < 10) {++zaj[int(d1)];  }
  //cout <<"d1 " << d1 << "\n";
  //cout << "d2 " << d2 << "\n";
 }
 rep(x,10)
 {
  cout << setw(4) << zaj[x] << " ";
 }
 return 0;
}


[brianfry713]

Input:

Code: Select all

1 1 1
255 255 255
0 0 0

AC Output

Code: Select all

   0   0   0   0   0   0   0   0   0   0