11039 - Building designing

[asif_rahman0]

percentage of submission is high!
but i m getting TLE.
why??
if i cut off sort() function then getting WA. so how can i reduce the TIME of this program?

plz help.

Code: Select all

removed

[Jan]

I used qsort() and got Accepted. You can try replacing your sort() function with qsort() function. May be the sort() function is too slow.

Hope it helps.

[arsalan_mousavian]

or you can use STL set

[asif_rahman0]

now tell me whts the reason to get TLE???
replaced the sort() with qsort().

Code: Select all

removed

[david]

I used qsort() and got Accepted. You can try replacing your sort() function with qsort() function. May be the sort() function is too slow.

Hope it helps.

The STL sort() function is usually quite a bit faster than qsort(), because it doesn't incur the overhead of comparison function calls (the compiler may inline them as the sort() code is templated).

[naffi]

Getting WA. Can anyone help me? I cleared the vectors after every case.

Code: Select all

      sort(pos.begin(),pos.end());
		sort(neg.begin(),neg.end());
		tmp = 0;
		if(pos.empty() || neg.empty())
		{
			tmp = 1;
		}		
		else if(pos.front()+neg.back()<0)
		{
			while(pos.front()+neg.back()<0 && !neg.empty() && !pos.empty())
			{
				tmp++;
				while(pos.front()+neg.back()<0 && !pos.empty())
				{
					pos.erase(pos.begin());
				}
				neg.pop_back();
				tmp++;
			}
			if(!pos.empty())tmp++;
		}		
		else
		{
			while(pos.front()+neg.back()>0 && !neg.empty() && !pos.empty())
			{
				tmp++;
				while(pos.front()+neg.back()>0 && !neg.empty())
				{
					neg.pop_back();
				}
				pos.erase(pos.begin());
				tmp++;
			}
			if(!neg.empty())tmp++;
		}

[plamplam]

Try this

Code: Select all

7
5
-1
-2
-3
-4
-5
5
1
2
3
4
5
2
5
-1
0
1
5
5
7
-2
6
9
-3
8
11
-9
2
5
18
17
-15
4

Output:

Code: Select all

1
1
2
0
1
2
5

[lastopier]

Any idea why this throws runtime error?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;


class Bd {
	
	
	
	StringTokenizer st=new StringTokenizer("");
	BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
	boolean hasNextToken() throws IOException{
		while(!st.hasMoreTokens()){
			String line=input.readLine();
			if(line==null)
				return false;
			st=new StringTokenizer(line);
		}
		return true;
	}
	
	String nextToken() throws IOException{
		if(hasNextToken())
			return st.nextToken();
		return null;
	}
	
	void run() throws NumberFormatException, IOException{
		ArrayList<ArrayList<Integer>> floors =new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> blue=new ArrayList<Integer>();
		ArrayList<Integer> red=new ArrayList<Integer>();
		int floorCount=Integer.parseInt(nextToken());
		
		if(floorCount<0)
			return;
		for(int i=0;i<floorCount;i++){
			int x=Integer.parseInt(nextToken());
			if(x>0)
				blue.add(x);
			if(x<0)
				red.add(Math.abs(x));
		}
		if(blue.isEmpty() || red.isEmpty()){
			if(blue.isEmpty() && red.isEmpty())
				System.out.println("0");
			else
				System.out.println("1");
			return;
		}
		Collections.sort(blue);
		Collections.sort(red);
		if(blue.get(0)<red.get(0)){
			floors.add(blue);
			floors.add(red);
		}else{
			floors.add(red);
			floors.add(blue);
		}
		System.out.println(findMaxFloorCount(floors));
		
	}
	
	int findMaxFloorCount(ArrayList<ArrayList<Integer>> floors){
		int currentColour=0;
		int maxFloorCount=0;
		int prev=0;
		while(true){
			if(floors.get(currentColour).isEmpty()){
				return maxFloorCount;
			}
			if(floors.get(currentColour).get(0)>prev){
				maxFloorCount++;
				prev=floors.get(currentColour).get(0);
				floors.get(currentColour).remove(0);
				if(currentColour==0){
					currentColour++;
				}else{
					currentColour--;
				}
				
				
			}
			else{
				if(floors.get(currentColour).isEmpty()){
					return maxFloorCount;
				}
				floors.get(currentColour).remove(0);
			}
		}
		
	}
	public static void main(String[] args){
		Bd instance=new Bd();
		int testCaseCount=0;
		try {
			testCaseCount = Integer.parseInt(instance.nextToken());
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
		} catch (IOException e) {
			// TODO Auto-generated catch block
		}
		for(int i=0;i<testCaseCount;i++){
			try {
				instance.run();
			} catch (NumberFormatException e) {
				// TODO Auto-generated catch block
			} catch (IOException e) {
				// TODO Auto-generated catch block
			}
		}
	}
	
	

}

[lastopier]

OK, if someone has similar problem, the class must be named "Main", which is a little silly and it's NOT mentioned in submission specifications. Also, don't do this in Java, it's waaay too slow.

[lighted]

It was written in Additional Information for Java specifications. http://uva.onlinejudge.org/index.php?op ... &Itemid=30

All programs must begin in a static main method in a Main class.
Do not use public classes: even Main must be non public to avoid compile error.