Im bir sorun kodlama (referans --http: //www.codechef.com/FEB11/problems/THREECLR/) aşıldı aşağıdaJava sorunu zaman sınırı sorunu
benim kodudur
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());}
}}
Bu kodu Ideone gibi çevrimiçi yargıçlarda kontrol ettim ve istenen sonuçları aldım. Ancak bu kodu gönderdiğimde, bir Zaman Sınırı hatası aştım. Bu kodu Ideone'da yeterince büyük bir giriş kümesiyle test ettim ve yürütme süresi 1 saniyeden daha azdı. Hayatımdan tüm mutluluğu süzmüş gibi görünen bir hata ya da hafıza sızıntısı var gibi görünüyor. Herhangi bir işaretçi/ipucu çok takdir edilecektir.
Teşekkür
Edit1 -
, ben aşağıdaki python komut dosyası tarafından oluşturulan girişli kod koştum yanıt çocuklar içinTeşekkür -
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()
Ve kod bir kuyruklu aldı Yukarıdaki betik tarafından sağlanan girdiyi yürütmek için 71052 milisaniye. Şimdi infaz süresini en az 8000 milisaniye indirmem gerekiyor. Hashfaps ve HashSet'leri rfeak tarafından önerilen şekilde değiştirmeyi denemeye çalışıyorum ve ayrıca bu senaryoda not almanın yardımcı olup olmayacağını merak ediyorum. Tavsiye lütfen.
EDIT2 - Algo'yu diziler kullanarak yeniden kodlamak işe yaramış görünüyor. Sadece aynı kodun farklı zamanlarda tekrar gönderilmesi bana Kabul Edilen Çözüm ve Süre sınırını aşmamı sağlar: D Biraz daha optimize etmek için hashmap'ları kullanmanın başka bir yolu var. Yardımcılar için teşekkürler!
çok daha büyük bir girdi beslediklerini ve kodunuzun işlenmesinin çok uzun sürdüğünü düşündünüz mü? –
Gönderdikleri veri kümesinin ne kadar büyük olduğunu biliyor musunuz? Bu veri setini bulabilir misin? –
Tahminimce gerçekleşmeyen bir girdi bekliyorsunuz veya programınızın sonsuz bir döngüye girmesine neden olan bir girdi var. –