New tests were added to the problem. First tests were replaced with examples from the problem statements. 106 authors have lost AC after the rejudge.

give me wrong test, please
{$n+}
[be ili ne be] spasibo toliany


Edited by author 10.01.2006 02:12

I have WA on test #2. Why? Here it is my code:

[It is was code here]

My mistake was a stupied missprint ;)

Edited by author 26.09.2005 14:31

This question merely touches this problem; however, i'm interested at, why c++ stack is working slower then vector? Being unable to accept solution using stack, i solved it with vector utilities; but why such simple structure as stack is so time devouring?

thx, mq

I can`t find place where it can be crash.

The 1th Collegiate Programming Contest
->
The 1st Collegiate Programming Contest

Can anybody help me with first test???

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;

class sset
{
public:
    int p, rank;
};

sset a[1010];

void init (int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        a[i].p = i;
        a[i].rank = 0;
    }
}

int fset (int x)
{
    if (x != a[x].p)
    {
        a[x].p = fset (a[x].p);
    }
    return a[x].p;
}

void sset_union (int x, int y)
{
    if (a[x].rank < a[y].rank)
    {
        a[x].p = a[y].p;
    }
    else
    {
        a[y].p = a[x].p;
        if (a[x].rank == a[y].rank)
        {
            a[x].rank++;
        }
    }
}

int n;
string v[1010];
int c[1010][4] = {0};
int arr[1010] = {0};

bool is_in (int i, int j)
{
    int cd;
    cd = (c[i][0]-c[j][0])*(c[i][0]-c[j][0]) + (c[i][1]-c[j][1])*(c[i][1]-c[j][1]) + (c[i][2]-c[j][2])*(c[i][2]-c[j][2]);
    int rd = c[i][3]+c[j][3];
    rd *= rd;
    return rd > cd;
}

int main ()
{
    //freopen ("a.in", "r", stdin);
    //freopen ("a.out", "w", stdout);
    int i, j;
    int di;
    int p, q;
    scanf ("%d", &n);
    init (n);
    for (i = 0; i < n; ++i)
    {
        scanf ("%d%d%d%d", &c[i][0], &c[i][1], &c[i][2], &c[i][3]);
        di = -1;
        for (j = i-1; j >= 0; --j)
        {
            if (is_in(i, j))
            {
                p = fset (i);
                q = fset (j);
                sset_union (p, q);
            }
        }
    }
    for (i = 0; i < n; ++i)
    {
        j = fset(i);
        if (v[j] == "")
        {
            v[j] = (char)(i+'0');
        }
        else
        {
            v[j] += ", ";
            v[j] += (char)(i+'0');
        }
    }
    sort (v, v+n);
    for (i = 0; i < n; ++i)
    {
        if (v[i] != "")
        {
            cout<<v[i]<<endl;
        }
    }
    return 0;
}

5
2 0 0 1
4 0 0 1
5 0 0 1
6 0 0 1
3 0 0 1

My accepted code outputs this answer:

0, 1, 4
2, 3

Obviously the right answer is 0, 1, 2, 3, 4

My corrected code got WA on test #34 (sbm.id 1787693)

Hi,Gues!

Please Help me! I have WA#54 and I don't understand what's wrong.

This is my code

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

struct sphere
{
    int x;
    int y;
    int z;
    int r;
    int num;
    bool met;
    sphere(){}
    sphere(int X,int Y,int Z,int R,int Num)
    {
        x = X;
        y = Y;
        z = Z;
        r = R;
        num = Num;
        met = false;

    }
} mas[1005];
int x,y,z,r;
int n;
string STR[1005];
int countSTR;
void input()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>x>>y>>z>>r;
        mas[i] = sphere(x,y,z,r,i);
    }
}
int posR;
int posW;
sphere Q[1005];
void Add(sphere sp)
{
    Q[posW++] = sp;
}
void zero()
{
    posR = 0;
    posW = 0;
    memset(Q,0,sizeof(Q));
}

bool isInter(sphere &a,sphere &b)
{
    int len = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z);
    int R = (a.r + b.r)*(a.r + b.r);
    if (len>=R)
        return false;
    return true;
}
void search(sphere sp)
{
    zero();
    sp.met = true;
    Add(sp);



    while(posR<posW)
    {
        sphere cur = Q[posR++];
        for (int i=0;i<n;i++)
        {
            if (mas[i].met == false)
                if (isInter(cur,mas[i]))
                {
                    mas[i].met = true;
                    Add(mas[i]);
                }
        }

    }
    int INT[1005];
    int countINT = 0;
    memset(INT,0,sizeof(INT));
    for (int i=0;i<posW;i++)
    {
        INT[countINT++] = Q[i].num;
    }
    sort(INT,INT+countINT);
    string str = "";
    char tmp[10];
    sprintf(tmp,"%i",INT[0]);
    str += tmp;
    for (int i=1;i<countINT;i++)
    {
        sprintf(tmp,"%i",INT[i]);
        str += ", ";
        str += tmp;
    }
    STR[countSTR++] = str;



}
void solve()
{
    for (int i=0;i<n;i++)
    {
        if (mas[i].met==false)
        {
            mas[i].met = true;
            search(mas[i]);
        }
    }
    sort(STR,STR + countSTR);
    for (int i=0;i<countSTR;i++)
    {
        cout<<STR[i]<<endl;
    }
}
int main()
{
    input();
    solve();
    return 0;
}

Condition of problem says that
"Two planets have stuck each other if they have at least one common point"
But sample #1 show that it must be
"Two planets have stuck each other if they have at least two common points" .
I used this fact and got AC.
Please, correct this.



Edited by author 15.07.2007 01:56

I have right solution but I have WA#1. Give me some tests!Please.

why do I get mem. limit exceeded at test #2? (3 626 KB) is there a way I could optimize this program? I declared 7 arrays x 1000 each, and a 1000x1000 matrix... :|

Edited by author 23.10.2005 15:51

Why you got AC first when I?
I only secondary.
I not happy.  :(

Sample #1
2
1 1 1 1
1 3 1 1

The planets have common point (1,2,1), but in output they are in different archipelagos.

"Two planets have stuck each other if they have at least one common point"

It should be "at least two common points"