Jul 2012
1 / 6
Jul 2012
Feb 2024
shailu_sof
Jul '12

Getting WA...plz help

#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long int intl;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
intl max(intl a,intl b)
{
    if(a>b)
    return a;
    else
    return b;
}
intl solve(intl ar[],intl mx1,intl m,intl n)
{
    intl l=0,r=mx1-1,wud,i,mi;
    while(l<r)
    {
        wud=0;
        mi=(l+r)/2;
        rep(i,n)
        wud+=max(ar[i]-mi,0);
       //if(wud==m)
       // return l;
        if(wud>m)
        {
            l=mi+1;
           // return l;
        }
        else
        r=mi-1;
    }
    return l;
}
int main()
{
    intl n,m,i,j,a;
    intl mx1=0LL;
    cin>>n>>m;
    intl ar[n];
    //cout<<n<<endl;
    i=0;
    rep(i,n)
    {
        cin>>ar[i];

}
i=0;
rep(i,n)
{
   if(ar[i]>mx1)
   mx1=ar[i];
}
//cout<<mx1<<endl;
intl ans=solve(ar,mx1,m,n);
cout<<ans;
return 0;
}

  • created

    Jul '12

  • last reply

    Feb '24
  • 5

    replies

  • 565

    views

  • 5

    users

  • 2

    links

leppyr64
Jul '12

Your issue is easy to illustrate with n=2.

I would be more worried about TLE here though. O(n^2logn) is really slow.

2 months later
nikoo28
Sep '12

Please help me with this code...why I am getting a WA..?? my solution works in O(nlog n) time... open_mouth astonished
please give me a test case where my algorithm fails...

#include<stdio.h>
#include<stdlib.h>
void exchange(long long *a,long long *b)
{
	long temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
long long partition(long long A[],long long si,long long ei)
{
	long long x=A[ei];
	long long i=(si-1);
	long long j;
	for(j=si;j<=ei-1;j++)
		if(A[j]<=x)
		{
			i++;
			exchange(&A[i],&A[j]);
		}
	exchange(&A[i+1],&A[ei]);
	return (i+1);
}
void quick(long long A[],long long si,long long ei)
{
	long long pi;
	if(si<ei)
	{
		pi=partition(A,si,ei);
		quick(A,si,pi-1);
		quick(A,pi+1,ei);
	}
}
int main(void)
{
	long trees;
	scanf("%ld",&trees);
	long long req;
	scanf("%lld",&req);
	int flag=0;
	long long *hts=(long long*)malloc(sizeof(long long)*trees);
	long i;
	long long max=0;
	for(i=0;i<trees;i++)
	{
		scanf("%lld",&hts[i]);
		max+=hts[i];
	}
	if(req==0)
		goto ab;
	flag=1;
	quick(hts,0,(trees-1));
	long long blade=0;
	long long dec=trees;
	long col=0;
	while(max>req)
	{
		max=max-dec;
		blade++;
		while(blade==hts[col])
		{
			col++;
			dec--;
		}
	}
	if(max<req)
		blade--;
ab:	if(flag)
		printf("%lld",blade);
	else
		printf("0");
	return 0;
}
20 days later
narbej
Oct '12

Maybe because its too little answers for too much questions wink ?
I don't know why you got WA, but from yours code I see that perhaps you don't know what is different between long long, long and int.
And maybe you find some tips in spoj.pl/forum/search.php?key ... mit=Search10

this is reason to get or not TLE, O(nlog n) have nothing with to got WA.

11 years later
kartikvr20
Feb '24

I am getting same WA error. Whats the issue here?

import java.util.Scanner;
import java.lang.Math;

public class EKO {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in1);
int n, m;
n = sc.nextInt();
m = sc.nextInt();
int[] trees = new int[n];
for (int i = 0; i < n; i++) {
trees[i] = sc.nextInt();
}
sc.close();
System.out.println(requiredHeight(trees, m));
}

static int requiredHeight(int[] trees, int maxWood) {
    int maxHeight = maxHeight(trees);
    int minHeight = 0;
    while (minHeight <= maxHeight) {
        int mid = minHeight + (maxHeight - minHeight) / 2;
        if (canCutMore(trees, mid, maxWood)) {
            maxHeight = mid - 1;
        } else {
            minHeight = mid + 1;
        }
    }
    return maxHeight;
}

static int maxHeight(int[] trees) {
    int maxHeight = 0;
    for (int i = 0; i < trees.length; i++) {
        maxHeight = Math.max(maxHeight, trees[i]);
    }
    return maxHeight;
}

static boolean canCutMore(int[] trees, int cuttingHeight, int maxWood) {
    int cutLength = 0;
    for (int i = 0; i < trees.length; i++) {
        if (trees[i] > cuttingHeight) {
            cutLength += (trees[i] - cuttingHeight);
        }
        if (cutLength > maxWood)
            return false;
    }
    return true;

}

}