Show all threads Hide all threads Show all messages Hide all messages |
Admin! How Come! TEST4 N-1? | deLarry | 1252. Sorting the Tombstones | 7 Aug 2020 18:41 | 2 |
It says, that K is an amount of stones BETWEEN other stones. Why does Test4 answer equal n-1. I suppose it should be n-2, shouldn't it? Edited by author 26.12.2016 16:46 You should read the problem statement more clearly. Since K<N, if the array is sorted then K=N-1. |
note for WA#4 | hoan | 1252. Sorting the Tombstones | 6 Dec 2019 15:47 | 4 |
you must sort in ascend and descend order !!! AC programm: 6 1 5 4 3 2 6 ans: 4 Edited by author 10.02.2011 11:10 |
test case for #6 WA | Craig Tucker | 1252. Sorting the Tombstones | 31 Oct 2017 02:47 | 1 |
6 1 3 2 6 5 4 answer: 0 Edited by author 31.10.2017 02:47 |
awful description | Craig Tucker | 1252. Sorting the Tombstones | 31 Oct 2017 02:26 | 1 |
it's one of the most awful descriptions of the problems i've ever seen. some corner cases, which are really questionable, are not explained. it really irritates because instead of solving the next problem you need to guess what the answer is. how should i know what is the answer for 1? i am not linguist, but smth tells me, that there are no situation when you can find elements in between in the list of one element. what is the answer? should i put 0, 1, etc? after all it's not a competition, i can't even ask the judge or stuff how should i interpret the problem itself. Edited by author 31.10.2017 02:27 |
Problem Statement Explained | KNIGHT0X300 | 1252. Sorting the Tombstones | 27 Jun 2013 10:41 | 1 |
Transposing means swapping two tombstones NOT reversing the order of all the stones between selected two. |
yet another note for WA4 | Aneto | 1252. Sorting the Tombstones | 9 Jan 2013 02:21 | 1 |
if stones are sorted then answer is n-1 It took me a while to find out this special case :) |
what's wrong WA#2 | tutuna | 1252. Sorting the Tombstones | 19 Sep 2012 16:19 | 1 |
# include <iostream> # include <cstdio> using namespace std; const int Maxn = 130012; int n, ans1, ans2, L1, L2, x, p[Maxn], q1, q2; int GCD (int a, int b){
if (b > a) return GCD(b, a); else if (b == 0) return a; else return GCD(b, a % b); } int main () { freopen ("1.txt", "r", stdin); freopen ("2.txt", "w", stdout); cin>>n; for (int i = 1; i <= n; i++){ cin>>x; p[x] = i; } q1 = 0; q2 = n + 1; ans1 = 0; ans2 = 0;
for (int i = 1; i <= Maxn; i++){ if (p[i] > 0) { q1 ++; q2 --; L1 = p[i] - q1; if (L1 < 0) L1 = -L1; L2 = p[i] - q2; if (L2 < 0) L2 = -L2; if (L1 > 0) if (ans1 > 0) ans1 = GCD(ans1, L1); else ans1 = L1; if (L2 > 0) if (ans2 > 0) ans2 = GCD(ans2, L2); else ans2 = L2;
}
} if (ans1 == 0) ans1 = n - 1; else ans1 --; if (ans2 == 0) ans2 = n - 1; else ans2 --; if (ans1 > ans2) cout<<ans1; else cout<<ans2; return 0; } Edited by author 19.09.2012 17:23 |
can someone please explain me the problem statement? | Anupam Ghosh,Bengal Engg and Sc Uni,MtechIT,2006-09,India | 1252. Sorting the Tombstones | 21 Aug 2009 13:20 | 1 |
I dont understand the problem itselk. what does K stands for? |
To admins: Tests are weak | Roman Atangulov | 1252. Sorting the Tombstones | 9 May 2009 21:10 | 2 |
For test 5 2 1 3 4 5 my AC program outputs 3 but it's obvious that it's wrong. Meanwhile my program using GCD gets WA... |
if you get WA 5 | Rumter (3) | 1252. Sorting the Tombstones | 22 Nov 2008 21:14 | 1 |
WA: ... ans = gcd (ans, d - 1) ... print (ans) AC: ... ans = gcd (ans, d) ... print (ans - 1) ;-) |
Please tell me how to prove! | PSV | 1252. Sorting the Tombstones | 6 Aug 2008 16:11 | 3 |
I've AC but I can't undestand how prove that GCD gives right answer? Come ON! Please I want to know Every stone may go to positions pos+K*x, pos - its original place, x - some integer, K - sought value. If for every stone its designated position is reachable (i.e. K divides abs(dst-src)), then stones are sortable - just bubble-sort each of K chains, and they are not sortable otherwise. So, the answer is GCD(dst-src) for all stones. Edited by author 06.08.2008 16:12 |
Maybe it will help you.... | Nechaev Ilya (Rybinsk SAAT) | 1252. Sorting the Tombstones | 6 Aug 2008 16:08 | 2 |
I got AC for this problem 2 minutes ago. OMG ! In this problem you can sort stones in incresing or descreasing order !! Edited by author 12.11.2006 02:59 Sample input requires decreasing order |
why wa on 4#test?where's the mistake | 徐竞欧 | 1252. Sorting the Tombstones | 6 Aug 2008 16:07 | 3 |
I don't know where the mistake is in my program.Please give me some tests that are difficult.I tried several tests I made but I can't find where is my mistake.Thank you very much!! First of all you must check If array if already sorted. In this case answer is (n-1). And hint: array can be sorted in decreasing or increasing order... |
look at this test | text32 | 1252. Sorting the Tombstones | 11 Nov 2005 07:42 | 2 |
The weights of all the stones are different |
:(( I`m going to get MAD what`s wrong indeed? (+) | Pasha | 1252. Sorting the Tombstones | 10 Nov 2005 05:01 | 4 |
Const Maxn = 130002; Var N, I, X, L, Ans : LongInt; P : Array[0..MaxN] of LongInt; Function GCD(X,Y:LongInt):LongInt; Begin If Y>X Then GCD:=GCD(Y,X) Else If Y=0 Then GCD:=X Else GCD:=GCD(Y, X MOD Y); end; begin Readln(N); For I := 1 To N Do Begin Read(X); P[X]:=I; End; X:=0; Ans:=0; For I := 1 To MaxN Do If P[I]>0 Then Begin Inc(X); L:=Abs(P[I]-X); If L>0 Then If Ans>0 Then Ans:=GCD(Ans,L) Else Ans:=L; End; If Ans=0 Then WriteLn(N-1) Else WriteLn(Ans-1); end. > Const > Maxn = 130002; > Var > N, I, X, L, Ans : LongInt; > P : Array[0..MaxN] of LongInt; > > Function GCD(X,Y:LongInt):LongInt; > Begin > If Y>X Then > GCD:=GCD(Y,X) > Else > If Y=0 Then > GCD:=X > Else > GCD:=GCD(Y, X MOD Y); > end; > > begin > Readln(N); > For I := 1 To N Do > Begin > Read(X); > P[X]:=I; > End; > X:=0; > Ans:=0; > For I := 1 To MaxN Do > If P[I]>0 Then > Begin > Inc(X); > L:=Abs(P[I]-X); > If L>0 Then > If Ans>0 Then > Ans:=GCD(Ans,L) > Else > Ans:=L; > End; > If Ans=0 Then > WriteLn(N-1) > Else > WriteLn(Ans-1); > end. Sorting may be also in descending order My mail address is aidin_n7@hotmai.com I will glad to meet you more Best Aidin Const Maxn = 1302; Var N, I, X, L, Ans,x2,l2,ans2: LongInt; P : Array[0..MaxN] of LongInt; Function GCD(X,Y:LongInt):LongInt; Begin If Y>X Then GCD:=GCD(Y,X) Else If Y=0 Then GCD:=X Else GCD:=GCD(Y, X MOD Y); end; begin Readln(N); For I := 1 To N Do Begin Read(X); P[X]:=I; End; X:=0; x2:=n; Ans:=0; ans2:=0; For I := 1 To MaxN Do If P[I]>0 Then Begin Inc(X); dec(x2); L:=Abs(P[I]-X); l2:=abs(p[i]-x2); If L>0 Then If Ans>0 Then Ans:=GCD(Ans,L) Else Ans:=L; If L2>0 Then If Ans2>0 Then Ans2:=GCD(Ans2,L2) Else Ans2:=L2; End; if ans=0 then ans:=n-1 else ans:=ans-1; if ans2=0 then ans2:=n-1 else ans2:=ans2-1; if ans>ans2 then writeln(ans) else writeln(ans2); end. sorry... i used some of your code.. |
GCD is rules!!! | I am get tester... | 1252. Sorting the Tombstones | 14 Oct 2005 14:42 | 1 |
AC(+) time 0.031 memory 660 kb |
Can someone give me some tests? | Danica Porobic | 1252. Sorting the Tombstones | 27 Jun 2005 22:58 | 2 |
Hi! I used sorting ( qsort ) and gcd but I keep getting WA ( #3 ). Please give me some tricky tests or if someone could please take a look on my code I'll send it to him/her. My e-mail dporobic@eunet.yu. You have to sort in ascenting and in descenting order |
Why we should use GCD in this problem? | BYF | 1252. Sorting the Tombstones | 30 Oct 2004 13:55 | 2 |
I've got AC, but I don't know the reason exactly. I just guessed it, and got AC. How about this case? 5 2 1 3 4 5 I think k could be 2 2 5 3 4 1 1 5 3 4 2 1 2 3 4 5 But my program output 0 Do I misunderstand this problem or something else? |
how can i get MLE? | testing~ | 1252. Sorting the Tombstones | 31 Jul 2004 13:31 | 3 |
// {$I+,Q+,R+,S-} program Sorting_the_tombstones ; const maxn = 130000; mask : longint = 30000; var i,j,k,n,kk,t,ss : longint; a : array[1..maxn]of integer; aa : array[1..maxn]of byte; b : array[0..maxn div 8]of byte; function gcd(a,b : longint ) : longint ; begin while b>0 do begin a:=a mod b; if a=0 then break; b:=b mod a; end; gcd:=a+b; end; begin //main; end. look i only use such few various...but the online judge said i used 1009kb!!why? You should use smallint instead of integer In some compiler integer=longint(4 bytes) Try smallint maybe you can get AC goodluck! Edited by author 31.07.2004 20:51 And because compiler uses about 350KB (-) |
WHY WHONG ANSWER ??????? | vano_B1 | 1252. Sorting the Tombstones | 10 Jul 2003 21:53 | 1 |
type maxm=1..130001; var m,p:array [1..130001] of maxm; n,i1,j1,l,k:longint; function nod(a,b:maxm):maxm; begin while (a<>0) and (b<>0) do if a>b then a:=a mod b else b:=b mod a; if a=0 then nod:=b else nod:=a; end; procedure swapl(var a,b:maxm); var d:maxm; begin d:=a; a:=b; b:=d; end; procedure sort(l,r:maxm); var i,j,x:maxm; begin i:=l; j:=r; x:=m[(r+l) div 2]; repeat while m[i]<x do inc(i); while m[j]>x do dec(j); if i<=j then begin swapl(m[i],m[j]); swapl(p[i],p[j]); inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin readln(n); for i1:=1 to n do readln(m[i1]); for i1:=1 to n do p[i1]:=i1; sort(1,n); l:=1; while (p[l]-l=0) and (l<>n+1) do inc(l); if l=n+1 then begin write(n-1); halt; end; k:=abs(p[l]-l); for i1:=l+1 to n do begin if p[i1]-i1=0 then continue; k:=nod(k,abs(p[i1]-i1)); end; write(k-1); end. |