http://acm.timus.ru/status.aspx?space=1&num=1510&author=107146

My first solution uses more than 67 kb only for data, but in result table there is 46 Kb.
Second solution uses for data structures about 260kb (192 kb more) but in result table - 438Kb
And third one uses about 20kb, in result table - empty cell.

Why so strange results?

is the problem as easy as it seems or there is some trick?
ACM problems r never easy except a very few which i have solved.please provide some test cases.

If you change the Memory Limit to some small value, for example 512K, the problem could be very funny.

Good luck~

Can anybody give some stress test for this task?pls

with such a large ML?

this algo with O(n*log(n))
but i don't know why WA on Test21, please help me!

[code deleted]

Edited by moderator 24.11.2019 13:39

I got AC with O(n) ! Several times I got TL, but when I stopped reading the input with java.util.Scanner and started using java.io.BufferedReader it worked.

java.util.Scanner is too slow, don't use it !

var
max,ll,o,i,j,l,m,n:longint;
k:real;
b,a:array[1..1000] of real;
begin
readln(n);
for i:=1 to n do
begin
read(k);
j:=j+1;
a[j]:=trunc(k);
end;
J:=0;
repeat
j:=j+1;
for i:=1 to n do
if a[j]=a[i] then  l:=l+1;
o:=o+1; b[o]:=l;
l:=0;
until j=n;
max:=trunc(b[1]);
ll:=1;
for i:=1 to o do
if b[i]>max then begin max:=trunc(b[i]);ll:=i; end;

write(trunc(a[ll]));
end.

#include<iostream>
#include<stack>
using namespace std;
stack < int > s;
int n,s1;
int main()
{
    scanf("%d",&n);
    while(n!=0)
    {                scanf("%d",&s1);
                    if(s.empty())s.push(s1);
                    else
                    {
                        if(s1==s.top())s.push(s1);
                        else if(!s.empty()) s.pop();
                    }
                    n--;
    }
    printf("%d\n",s.top());
     return 0;
}

Could anyone tell me why it WA#2?


program p1510_Use_QSort;

var
  d:array[1..500000]of longint;
  n,i,j,max,maxh:longint;

procedure qsort(s,t:longint);
  var
    i,j,p:longint;
  begin
  //make it randomize
    p:=random(t-s)+s+1;
    d[s]:=d[s] xor d[p];
    d[p]:=d[s] xor d[p];
    d[s]:=d[s] xor d[p];
  //start sort
    i:=s;j:=t;
    while true do begin
      while (i<j)and(d[i]<=d[j]) do dec(j);
      if i=j then break;
      d[i]:=d[i] xor d[j];d[j]:=d[i] xor d[j];d[i]:=d[i] xor d[j];
      while (i<j)and(d[i]<=d[j]) do inc(i);
      if i=j then break;
      d[i]:=d[i] xor d[j];d[j]:=d[i] xor d[j];d[i]:=d[i] xor d[j];
    end;
    dec(i);inc(j);
    if s<i then qsort(s,i);
    if j<t then qsort(j,t);
  end;

begin
  readln(n);
  for i:=1 to n do read(d[i]);
  randomize;
  qsort(1,n)
  writeln(d[n shr 1+1]);
end.

this is my code:


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{  long  K[5000005],N,i,j,t,value,k,count,a,flag;
            scanf ("%ld",&N);
            if (N%2==0) k=N/2;
            else k=N/2+1;
            for (i=0;i<N;i++)
                     scanf("%ld",&K[i]);
            for(i=0;i<N;i++){
                    j=rand()%N;
                    for(flag=0,count=1,t=0;t<N;t++){
                            if (K[t]==K[j])
                                    count++;
                            if (count>=k){
                                     value=K[j];
                                     flag=1;
                                     break;
                            }
                    }
                    if (flag=1) break;
             }
            printf("%ld\n",value);
 return 0;
}

why  Crash (stack overflow)?

please help me ?

I thing in this problem impossible get WA.
TLE I understand. But...
What wrong.
I use Qsort and dihotomy.
Can anyone give me some interesting tests?
Thank's!
;)

#include<iostream>
#include<algorithm>
using namespace std;
int used[500000]={0};
bool cmp(int a,int b)
{
     return (a>b);
}
int main (void)
{
    int N;
    cin>>N;
    for (int k=0;k<N;k++)
    {
        int f;
        cin>>f;
        used[f]++;
    }
    sort (used,used+500000,cmp);
    cout<<used[0]<<endl;
    return 0;
}

i can't understand what is wrong(((

var
k:array[1..3] of integer;
t:array[1..3] of integer;
kt:byte=0;
c,i,n:integer;
begin
readln(n);
if n<3 then begin readln(c); writeln(c); end else
begin
kt:=0;
for i:=1 to 3 do t[i]:=0;
for i:=1 to n do
 begin
  read(c);
  if kt<3 then
   begin
    if kt=0 then begin t[1]:=c; inc(kt); end else
     begin
      if (kt=1) and (t[1]<>c) then
       begin
        inc(kt);
        t[2]:=c;
       end;
      if (kt=2) and (t[1]<>c) and (t[2]<>c) then
       begin
        inc(kt);
        t[3]:=c;
       end;
     end;
   end;
 if c=t[1] then inc(k[1]);
 if c=t[2] then inc(k[2]);
 if c=t[3] then inc(k[3]);
 end;
c:=1;
n:=k[1];
for i:=2 to 3 do
 if k[i]>n then
  begin
   c:=i;
   n:=k[i];
  end;
writeln(t[c]);
end;
{if k[1]>n div 2 then writeln(t[1]);
if k[2]>n div 2 then writeln(t[2]);
if k[3]>n div 2 then writeln(t[3]);
readln;}
end.

Hi.
I have WA on test #2. Can you post some samples? Thanks.

Edited by author 17.03.2007 22:05

Edited by author 17.03.2007 22:05

Edited by author 17.03.2007 22:49

var
b,a:array[1..100] of string;
x,l,w,n,i,j:integer;
begin
  assign(input,'fac.in');reset(input);
  assign(output,'fac.out');rewrite(output);
  readln(n);
    for i:=1 to n do
      readln(a[i]);
      for i:=1 to n do
         for j:=i+1 to n do
            begin
              if (a[i]=a[j]) and (a[i]<>'0') and (a[j]<>'0') then
                begin
                   x:=x+1;
                   b[x]:=a[i];
                   for l:=1 to n do
                   if b[x]=a[l] then a[l]:='0';
                end;
            end;
      for i:=1 to x do writeln(b[i]);

  close(input);close(output);
end.

Edited by author 19.03.2007 14:49

Why this source got WA#13

var a:array[1..5000]of longint;
n,k,i,j,l,r,mid,com,cout:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin i:=l; j:=r; x:=a[(l+r) DIV 2];
repeat
while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
if i<=j then
begin y:=a[i]; a[i]:=a[j]; a[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin read(n);
for i:=1 to n do
read(a[i]);
sort(1,n);
mid:=-maxlongint;
cout:=1; com:=0;
for i:=2 to n do
if a[i]=a[i-1] then inc(cout)
else if cout>mid then
begin mid:=cout;
cout:=1;
com:=a[i-1];
end;
if ((com=0)and(n>0)) then com:=a[1]
else
if (mid<cout) then com:=a[n]
else
if ((com=0)and(n=0)) then com:=0;

write(com);
end.

Edited by author 16.03.2007 10:55