11039 - Building designing

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

11039 - Building designing

Post by asif_rahman0 » Sun Jun 04, 2006 3:30 pm

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
Last edited by asif_rahman0 on Sun Jun 04, 2006 4:37 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jun 04, 2006 3:56 pm

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Jun 04, 2006 4:03 pm

or you can use STL set :wink:

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sun Jun 04, 2006 4:42 pm

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

Code: Select all

removed

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Jun 10, 2006 8:24 pm

Jan wrote: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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

11039 - Building designing WA

Post by naffi » Mon Sep 15, 2008 4:16 am

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++;
		}
Always At Your Help.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11039 - Building designing

Post by plamplam » Sat Jun 09, 2012 12:04 am

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
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

lastopier
New poster
Posts: 2
Joined: Sun Oct 19, 2014 11:49 am

Re: 11039 - Building designing

Post by lastopier » Sun Oct 19, 2014 11:51 am

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
New poster
Posts: 2
Joined: Sun Oct 19, 2014 11:49 am

Re: 11039 - Building designing

Post by lastopier » Sun Oct 19, 2014 8:39 pm

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11039 - Building designing

Post by lighted » Mon Oct 20, 2014 3:21 pm

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 110 (11000-11099)”