152 - Tree's a Crowd

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

My mistake. Sorry. :oops:
Please delete this post.

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz »

Larry wrote: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
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

152 - Runtime error

Post by 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
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

Re: 152 WA, please help

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 152 - Runtime error

Post by 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
Check input and AC output for thousands of problems on uDebug!

mic122
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

Re: 152 - Runtime error

Post by mic122 »

For this in my output is the same

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 152 WA, please help

Post by 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
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 152 - Runtime error

Post by brianfry713 »

Yes but you produce a RE.
Check input and AC output for thousands of problems on uDebug!

mic122
New poster
Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

Re: 152 - Runtime error

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 152 - Runtime error

Post by 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
Check input and AC output for thousands of problems on uDebug!

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 152 - Tree's a Crowd

Post by 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.
Last edited by sampad74 on Wed Jan 28, 2015 12:02 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 152 - Tree's a Crowd

Post by brianfry713 »

That is AC code.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”