ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1424. Minibus

WA #5
Posted by Igor Mihajlovic 10 Sep 2008 20:56
i use a lecture hall algo
here it is:
#include <iostream.h>

struct Putnik
{
int s;
int f;
int b;
int br;
};

int min(int x,int y)
{
return x<y?x:y;
}

void merge(Putnik *a,int f,int s,int n)
{

int i,j,k;
Putnik *b;
b=new Putnik[n-f];
k=0;
i=f;
j=s;
while(i<s && j<n)
{
if (a[i].f<a[j].f) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<s) b[k++]=a[i++];
while(j<n) b[k++]=a[j++];
for(i=0;i<k;i++)
a[i+f]=b[i];
delete [] b;

}

main()
{
int n,k,m,p,i,j,z,l,mn;
Putnik pt;
Putnik *a;
cin >>n>>m>>k>>p;
a=new Putnik[k];
for(i=0;i<k;i++)
{
cin>>a[i].s;
cin>>a[i].f;
a[i].b=1;
a[i].br=i+1;
}

for(i=1;i<k;i*=2)
for(j=0;j<k;j+=2*i)
if (j+i<k) merge(a,j,j+i,min(k,j+2*i));

z=k;
for(i=0;i<m && z;i++)
{
l=0;
while(a[l].b==0) l++;
pt=a[l];
a[l].b=0;
z--;
for(j=l+1;j<k;j++)
if (a[j].b && a[j].s>=pt.f)
{
z--;
a[j].b=0;
pt=a[j];
}

}

mn=(k-z)*p;
cout<<mn<<"\n";
for(i=0;i<k;i++)
if (a[i].b==0) cout<<a[i].br<<" ";

delete [] a;

}

and get wa# 5
i dont see a bug here plz help me
some tests would be nise also

Edited by author 10.09.2008 21:58
Re: WA #5
Posted by partisan 14 Nov 2008 19:56
Try this:
10 2 4 1
1 4
1 1
4 5
3 6

4
1 2 3 4
Re: WA #5
Posted by Igor Mihajlovic 16 Nov 2008 06:22
tried
it's ok
still wa

Edited by author 16.11.2008 06:23

Edited by author 16.11.2008 06:23
Re: WA #5
Posted by RASTA 21 Apr 2009 16:53
10 3 10 1
1 2
2 6
1 6
3 6
4 6
5 6
1 3
7 9
1 4
1 5

output
7
1 7 9 6 2 5 8
Re: WA #5
Posted by 3a[3.141592..]Jlu 19 Jul 2009 23:55
test :
10 2 4 1
1 4
1 1
4 5
3 6

is incorrect!!! S[i] < F[i] ;)
Re: WA #5
Posted by archi 26 Aug 2009 21:18
this test is incorrect:
s[i] != f[i] !!
Re: WA #5
Posted by Igor Mihajlovic 19 Sep 2009 05:58
thx
it was a dum error
i passed test 5
but wa7 now idk why