1196 - Tiling Up Blocks

[300pounddog]

Hi there. I can't seem to find out whats causing the WA with my code. Help please? Also, any tips on troubleshooting effectively? I think I am weak in thinking of the corner cases...
Thanks a lot.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,temp,maxx;
vector< pair<int,int> > blocks;
vector<int> dp;
struct sort_pred {
bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
if(left.first == right.first) return left.second < right.second;
return left.first < right.first;
}
};

int main(){
scanf("%d",&n);
do{

maxx=0;

blocks.clear();
blocks.assign(n,make_pair(0,0));
dp.clear();
dp.assign(n,0);
for(int w=0;w<n;w++){
scanf("%d %d",&blocks[w].first,&blocks[w].second);
}


sort(blocks.begin(), blocks.end(), sort_pred());

dp[0] = 1;

for(int q=1;q<n;q++){
for(int w=0;w<q;w++){

if(blocks[q].first >= blocks[w].first && blocks[q].second >= blocks[w].second){

dp[q] = max(dp[q],dp[w]+1);
if(dp[q]>maxx)maxx=dp[q];
}
}
}

printf("%d\n",maxx);

scanf("%d",&n);
}while(n!=0);
printf("*\n");

return 0;
}

[brianfry713]

Try a case where n = 1.

[300pounddog]

Try a case where n = 1.

Oh silly me. Thanks a ton. ACed immediately!

[brianfry713]

That is AC code

[Neo_1234]

GOT AC ..
MANY MANY THANKS TO BRIANFRY

[brianfry713]

Change line 14 to:
return (p.l > l || (p.l == l && p.m > m));

[lawrencealgorithm]

Anyone help me please!! My code is now Wrong Answer, however, I can't find anything wrong in my code. I know my code is long, but please help me troubleshoot this. Thank you very much.

Code: Select all

var
  l,m:array[1..10000] of integer;
	d:array[0..10001] of integer;
	n,k:integer;
	
procedure	enter();
var
	i:integer;
begin
	readln(n);
	for i:=1 to n do readln(l[i],m[i]);
end;

procedure	swap(var x,y:integer);
var
	tmp:integer;
begin
	tmp:=x;
	x:=y;
	y:=tmp;
end;

procedure	sort(lt,rt:integer);
var
	i,j,pp:integer;
	pvt1,pvt2:integer;
begin
	i:=lt;
	j:=rt;
	pp:=random(rt-lt+1)+lt;
	pvt1:=l[pp];
	pvt2:=m[pp];
	repeat
    while (l[i]<pvt1) or ((l[i]=pvt1) and (m[i]<pvt2)) do inc(i);
    while (l[j]>pvt1) or ((l[j]=pvt1) and (m[j]>pvt2)) do dec(j);
		if (i<=j) then
		begin
			swap(l[i],l[j]);
      swap(m[i],m[j]);
			inc(i);
			dec(j);
		end;
	until	(i>j);
	if (lt<j) then sort(lt,j);
	if (i<rt) then sort(i,rt);
end;

function	search(x:integer):integer;
var
	lt,rt,mid:integer;
begin
	lt:=1;
	rt:=k;
	while (lt<=rt) do
	begin
		mid:=(lt+rt)>>1;
		if (x>=d[mid-1]) and (x<d[mid]) then exit(mid);
		if (x>=d[mid-1]) then lt:=mid+1 else rt:=mid-1;
	end;
	exit(-1);
end;

procedure	solve();
var
	i,j:integer;
begin
	sort(1,n);
	k:=1;
	d[0]:=0;
	d[1]:=10001;
	for i:=1 to n do
	begin
    j:=search(m[i]);
    d[j]:=m[i];
		if (j=k) then
		begin
			inc(k);
			d[k]:=10001;
		end;
	end;
	writeln(k-1);
end;

procedure	main();
begin
	randomize;
	while (true) do
	begin
		enter();
		if (n=0) then
		begin
			write('*');
			break;
		end;
		solve();
	end;
end;
	
begin
	main();
end.

[brianfry713]

Always print a newline char at the end of the last line.

[lawrencealgorithm]

Always print a newline char at the end of the last line.

Thank you very much. I'm AC now.

[bradd123]

Why Runtime Error for this code? I can't figure out.

Code: Select all

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 10010
struct block{
    int l;
    int m;
};
block a[MAX];
int val[MAX];
bool compare(const block& lhs, const block& rhs){
    return lhs.l<=rhs.l;
}
int lis(int n){
    if(n==0) return val[n]=1;
    if(val[n]!=-1) return val[n];
    int max=0;
    for(int i=0;i<n;i++){
        if(a[i].m<=a[n].m){
            int temp=lis(i);
            if(max<temp) max=temp;
        }
    }
    return val[n]=max+1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    while(scanf("%d",&n)&&n!=0){
        memset(val,-1,sizeof val);
        for(int i=0;i<n;i++){
            scanf("%d %d",&a[i].l,&a[i].m);
        }
        sort(a,a+n,&compare);
        int total=0;
        for(int i=0;i<n;i++){
            int temp=lis(i);
            if(total<temp) total=temp;
        }
        printf("%d\n",total);
    }
    printf("*\n");
}

[brianfry713]

bradd123, I changed your compare function: https://ideone.com/zumUOn