|
|
back to boardWA11 ?? Posted by tester 3 Jan 2006 23:23 Here's my code. It gets WA11. Algo: the rightmost number of the current subarray[i..j] is a root of a subtree. The left branch includes those and only those numbers which are less than root; right branch - numbers greater than root. So if we swap these branches in our array and process them recursively we'll get the desired answer. Example: 1 7 5 (left br.) 21 22 27 25 20 (right br.) 10 (root) 1 (lb) 7 (rb) 5 (rt) empty (lb) 21 22 27 25 (rb) 20 (rt) 21 22 (lb) 27 (rb) 25 (rt) 21 (lb) empty (rb) 22 (rt) result: 27 21 22 25 20 7 1 5 10 proc "tree" does all the work. del is the delimiter of the branches. I've used the most primitive algo to swap the subarrays to simplify the solution.
program parliament; {$APPTYPE CONSOLE} var n,i:integer; a,t:array[1..100000] of integer; procedure tree(i,j:integer); var q,del:integer; begin if j>=i then begin del:=j-1; while (del>=i) and (a[del]>a[j]) do dec(del); for q:=del+1 to j-1 do t[q+i-del-1]:=a[q]; for q:=i to del do t[q+j-1-del]:=a[q]; for q:=i to j-1 do a[q]:=t[q]; tree(i,j-del-1); tree(j-del,j-1); end; end; begin fillchar(t,sizeof(t),0); read(n); for i:=1 to n do read(a[i]); tree(1,n); for i:=1 to n do write(a[i],' '); end. Re: WA11 ?? Posted by snake 10 Jan 2006 10:59 So, I also have WA11! What is wrong? I cant understand... {$APPTYPE CONSOLE} type Tchild=record a,b:word; end; var n,i:longint; ar:array[1..4000] of word; ch:array[1..4000] of Tchild; procedure write0; var child,oc:longint; begin child:=1; oc:=1; while (ch[child].a<>0)or(ch[child].b<>0) do begin oc:=child; if ch[child].b<>0 then child:=ch[child].b else child:=ch[child].a; end; if ch[oc].a=child then ch[oc].a:=0; if ch[oc].b=child then ch[oc].b:=0; write(ar[child],' '); ar[child]:=0; end; procedure write1; var child,oc:longint; begin child:=1; oc:=1; while (ch[child].a<>0)or(ch[child].b<>0) do begin oc:=child; if ch[child].a<>0 then child:=ch[child].a else child:=ch[child].b; end; if ch[oc].a=child then ch[oc].a:=0; if ch[oc].b=child then ch[oc].b:=0; write(ar[child],' '); ar[child]:=0; end; procedure swap(var a,b:word); var w:word; begin w:=a; a:=b; b:=w; end; procedure getplace(x,i:longint); var old,p,child:longint; begin p:=1; while true do begin if (x>ar[p])and(ch[p].b=0) then begin ch[p].b:=i; exit; end; if (x<ar[p])and(ch[p].a=0) then begin ch[p].a:=i; exit; end; if (x>ar[p]) then begin p:=ch[p].b; continue; end; if (x<ar[p]) then begin p:=ch[p].a; continue; end; end; end; begin fillchar(ch,sizeof(ch),0); readln(n); for i:=1 to n do read(ar[i]); for i:=1 to n div 2 do swap(ar[i],ar[n-i+1]); for i:=2 to n do getplace(ar[i],i); if n mod 2=1 then begin for i:=1 to n do write0; end else begin for i:=n downto 1 do write(ar[i],' '); end; end. Re: WA11 ?? The other realization of the same algo is AC. But where is the mistake here? Re: WA11 ?? Posted by hatred 27 Oct 2010 15:51 Why WA???????????????? #define clr(x,y) memset(x,y,sizeof(x)) using namespace std; int a[400000]; int a1[400000],a2[400000]; int s[400000]; int n; bool cmp(int x,int y) { return a[x]<a[y]; } int main(void) { freopen("input.in","r",stdin); freopen("output.out","w",stdout); cin >>n; if (n<1)return 0; for (int i=0;i<n;i++) { scanf("%d",&a[i]); } int k1=0,k2=0; for (int i=0;i<n-1;i++) if (a[n-1]>a[i]) { a1[k1++]=i; } else { a2[k2++]=i; } int t=-1; bool f=0; if (k2!=0) { sort(a2,a2+k2,cmp);
for (int i=k2-2;i>=0;i--) { // cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl; if (a2[i+1]<a2[i]) { if (f) { s[++t]=a2[i+1]; while (t>=0)cout << a[s[t--]]<< " "; }else cout << a[a2[i+1]]<< " "; f=0; } else { s[++t]=a2[i+1]; f=1; } }
s[++t]=a2[0]; while (t>=0)cout << a[s[t--]]<< " "; } t=-1; f=0; if (k1!=0) { sort(a1,a1+k1,cmp); for (int i=k1-2;i>=0;i--) { // cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl; if (a1[i+1]<a1[i]) { if (f) { s[++t]=a1[i+1]; while (t>=0)cout << a[s[t--]]<< " "; }else cout << a[a1[i+1]]<< " "; f=0; } else { s[++t]=a1[i+1]; f=1; } }
s[++t]=a1[0]; while (t>=0)cout << a[s[t--]]<< " "; } cout << a[n-1]; return 0; } Edited by author 27.10.2010 15:51 |
|
|