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
Moderator: Board moderators
Code: Select all
removed
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).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.
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++;
}
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
Code: Select all
1
1
2
0
1
2
5
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
}
}
}
}
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.