6
임 문제를 코딩 (참조 --http : //www.codechef.com/FEB11/problems/THREECLR/)를 초과 아래자바 문제가 시간 제한 문제
을 내 코드는
import java.io.*;
import java.util.*;
public class Main {
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
public static boolean iscontains(HashMap<Integer,HashSet<Integer>> resultmap,HashSet<Integer> b, int index)
{
boolean result=false;
for(Iterator<Integer> iter = b.iterator();iter.hasNext();)
{ int tmp=Integer.valueOf(iter.next().toString());
if(resultmap.get(index).contains(tmp))
result=true;
}
return result;
}
public static void main(String[] args) throws InterruptedException, FileNotFoundException {
try {
HashMap<Integer,HashSet<Integer>> pairlist = new HashMap<Integer,HashSet<Integer>>();
String input=null;
StringTokenizer idata;
int tc=0;
input=Main.ReadLn(255);
tc=Integer.parseInt(input);
while(--tc>=0)
{
input=Main.ReadLn(255);
idata = new StringTokenizer (input);idata = new StringTokenizer (input);
int dishnum= Integer.parseInt(idata.nextToken());
int pairnum= Integer.parseInt(idata.nextToken());
while (--pairnum>=0)
{
input=Main.ReadLn(255);
idata = new StringTokenizer (input);idata = new StringTokenizer (input);
int dish1=Integer.parseInt(idata.nextToken());
int dish2=Integer.parseInt(idata.nextToken());
if(pairlist.containsKey((Integer)dish1))
{
HashSet<Integer> dishes=new HashSet<Integer>();
dishes=pairlist.get(dish1);
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
else
{
HashSet<Integer> dishes=new HashSet<Integer>();
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
}
int maxrounds=1;
HashMap<Integer,HashSet<Integer>> resultlist = new HashMap<Integer,HashSet<Integer>>();
HashSet<Integer> addresult=new HashSet<Integer>();
addresult.add(1);
resultlist.put(1,addresult);
System.out.print("1");
for(int i=2;i<=dishnum;i++)
{
boolean found_one=false;
boolean second_check=false;
int minroundnum=maxrounds;
boolean pairlistcontains=false;
pairlistcontains=pairlist.containsKey(i);
for(int j=maxrounds;j>=1;j--)
{
if(!found_one){
if(pairlistcontains)
{
if(!iscontains(resultlist,pairlist.get((Integer) i),j))
{
for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
{
if(pairlist.get(resultiter.next()).contains(i))
second_check=true;
}
if(second_check==false)
{
found_one=true;
minroundnum=j;
j=0;
//second_check=false;
}
}
}
else
{
for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
{
if(pairlist.get(resultiter.next()).contains(i))
second_check=true;
}
if(second_check==false)
{
found_one=true;
minroundnum=j;
j=0;
//second_check=false;
}
}
second_check=false;
}
}
if((minroundnum==maxrounds)&&(found_one==false))
{
++minroundnum;
++maxrounds;
}
else
{
found_one=false;
}
HashSet<Integer> add2list=new HashSet<Integer>();
if(resultlist.containsKey(minroundnum))
{
add2list=resultlist.get(minroundnum);
add2list.add(i);
}
else
{
add2list.add(i);
}
resultlist.put(minroundnum,add2list);
System.out.print(" ");
System.out.print(minroundnum);
}
if((tc !=-1))
System.out.println();
}
}
catch(Exception e){System.out.println(e.toString());}
}}
Ideone과 같은 온라인 심사 위원에서이 코드를 확인하고 원하는 결과를 얻었습니다. 하지만이 코드를 제출하면 시간 제한 초과 오류가 발생합니다. 필자는 Ideone에이 코드를 충분히 큰 입력 집합으로 테스트했으며 실행에 걸린 시간은 1 초 미만이었다. 그것은 내 인생에서 모든 행복을 흘린 것처럼 보이는 버그 나 메모리 누수가있는 것 같습니다. 모든 도움말/팁을 크게 높이세요.
감사
EDIT1은 -
, 나는 다음과 같은 파이썬 스크립트에 의해 생성 된 입력 코드를 실행 한 대답들에 대한감사 -
import random
filename="input.txt"
file=open(filename,'w')
file.write("50")
file.write("\n")
for i in range(0,50):
file.write("500 10000")
file.write("\n")
for j in range(0,10000):
file.write(str(random.randrange(1,501))+" "+str(random.randrange(1,501)))
file.write("\n")
file.close()
그리고 내 코드는 무려했다 위의 스크립트에서 제공 한 입력에서 실행하려면 71052 밀리 초. 이제 실행 시간을 8000 밀리 초로 줄여야합니다. Im는 rfeak가 제안한대로 HashMaps와 HashSet을 대체하려고 노력하고 있으며,이 시나리오에서는 메모 작성이 도움이되는지 궁금합니다. 제발 조언.
EDIT2 - 어레이를 사용하여 내 고문을 재 코딩 한 것 같습니다. 단지 다른 시간에 동일한 코드를 다시 제출하면 Accepted Solution과 Time Limit가 초과됩니다. D 조금 더 최적화하기 위해 해시 맵을 사용하는 다른 방법이 있습니다. 도움 주셔서 감사합니다.
당신은 훨씬 더 큰 입력을 먹고 있으며 코드가 처리하는 데 너무 오래 걸리는 것으로 생각 해본 적이 있습니까? –
그들이 제출하는 데이터 세트의 크기가 얼마나되는지 알고 계십니까? 그 데이터 세트를 얻을 수 있습니까? –
내 추측으로는 발생하지 않는 입력을 기대하고 있거나 프로그램이 무한 루프에 빠지게하는 입력이 있다고 생각합니다. –