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 test 2 1 1 1 2 3 3 3 1 Answer 0, 1 You mistake on this line s2:=sqr(r[i]+r[t]); Understand What wrong? But you again got Wa1. :) i find test where you program with strange output 4 1 1 1 1 5 6 3 2 3 4 2 5 1 3 5 2 Answer: "no comments" sqr(r[i]+r[t]) - this ok zamena h:=m[i]; m[i+1]:=m[i]; m[i]:=h; :)) wa52:) Why answer is 0, 1??? Distance between centers of planets is bigger then sum of radiuses! answer 0 1 sqrt(4+4+4)>2+1 tolian lol:) ofCouse Answer is 0 1 I Write When s2:=sqr(r[i]+r[t]); <=Mistake here correct s2:=r[i]+r[t]; <=it correct. At last you have received AC. P.S. My code only 775 bytes.
And don't use squareRoot. Compute in sqr =) I get WA 1 because I forgot to sort stars in each archipelago when I output stars. =) Edited by author 17.05.2012 16:19 Edited by author 17.05.2012 16:20 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 I tried to submit your code... And I've got AC :) Your code: ... for (k = j; k < n; ++k) if (Component[k] == t) ... Right code: ... for (k = 0; k < n; ++k) if (Component[k] == t) ... So if your change only one symbol you'll also get AC :) Thank you! Well... I idin't see any mistakes, but there are some, as I got WA2. So Can you give a test? Well, please delete the code:) And what a simple problem!! 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 still wait for answer... Edited by author 20.07.2007 15:31 I have right solution but I have WA#1. Give me some tests!Please. Maybe you don't sort the output. Read the output format more carefully. Thaks. I got AC. Edited by author 13.12.2006 00:02 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... :| Hello, Vlad This problem is quite easy. You don't have to use the adjacency matrix. Just think at disjoint sets and path compression. Declare a "sphere" type and write a function to test the intersection between two spheres. Edited by author 25.03.2006 13:34 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" |
|