152 - Tree's a Crowd

[rickyliu]

IIRC, the initialization may only initialize the first element in C to 0. But in C++, it should initialize all elements to 0 according to the standard. I did use -Wall when compiling but no warning messages were received.

Anyway, I have changed the initialization of result[10] to the one you suggested and submitted it to the judge again. I got the same result, ie, C is AC and C++ is WA. My C++ compiler, GCC (v3.4.2 mingw-special), again behaved very strange. Without the optimization flag -O2, it showed the incorrect result in the first output (should be 4 but it showed 5). With the flag, it showed the correct result. Very weird. Is the judge GCC or its variants? I am pretty sure this is the issue of the C++ compiler.

[little joey]

IMO if 1000+ submissions are accepted, you may be certain that something is wrong with your code, not with the judge, so "Bugs and Suggestions" is not the right place to discuss it.

Your code is not able to take 5000 inputs plus the additional line containing zeros. Maybe this is less critical for the C compiler then for the C++ compiler. Anyways, change the array size and you'll get accepted, even with the C++ code.

[rickyliu]

My mistake. Sorry.
Please delete this post.

[rickyliu]

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

[Robert Gerbicz]

Finding the closest neighbor is O( n log n ), since you can find the Voronnoi diagram/Delaunacy Triangulation of the plane in O( n log n), and since it's a planar graph, it takes O( n )...

But the problem is 3 dimensional and for that in general case it is proven that there is no faster than O(n^2) algorithm to compute that spheres . In fact in d dimensional there is no faster than O(n^(ceil(d/2))).

[mic122]

Hi guys !

I've tried my programme on many cases and it finishes his work properly at my comp's. Just sending this code to Uva i get 'Runtime error'.

Please, check my code and tell what can be wrong, coz i'm just sick and tired of getting 'WA' or 'runtime error' sending almost every problem here -_- .

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
{
 int x,y,z;
 void m(int ex, int ey, int ez)
 {
  x = ex; y = ey; z = ez;
 }
};
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()
{ int x,y,z;
vector <int> zaj; zaj.resize(10,0);
 do
 {
  cin >> x >> y >> z;
  tr a; a.m(x,y,z); D.insert(a);
 } while (! (x == 0 && y == 0 && z == 0));
 D.erase(D.begin());
 for (set<tr,cmp>::iterator it = D.begin(); it != D.end(); it++)
 {
  double d1 = -1,d2 = -1; tr d; tr 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] << " ";
 }
  cout << "\n";
  zaj.clear();
  D.clear();
 return 0;
}

[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:
1 1 1
255 255 255
0 0 0

AC output:

Code: Select all

   0   0   0   0   0   0   0   0   0   0

[mic122]

For this in my output is the same

[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

[brianfry713]

Yes but you produce a RE.

[mic122]

Once I had RE but now all runs ok here...

Aaargh... For the following input :

Code: Select all

10 10 0
10 10 0
255 255 255
1 1 1
0 0 0

It wrote :

Code: Select all

 2 0 0 0 0 0 0 0 0 0

(ofc with the spaces)

[brianfry713]

For input:

Code: Select all

10 10 0
10 10 0
255 255 255
1 1 1
0 0 0

AC Output:

Code: Select all

   2   0   0   0   0   0   0   0   0   0

[sampad74]

got ac.thanks brian.i did not write " return 0" at the end of my program.may be for that reason i got WA.

[brianfry713]

That is AC code.