Re: ACM 10789 ... 又是一個Wrong Answer

[costbook (CB)]

嗯...雖然解出來了，不過有個時間最佳化的問題，


這是一小段code

         //如果字元出現次數為質數，則印出該字元
         for(int i=48;i<ASCII_PRINTABLE_MAX;i++){
            if(ascii[i]>1 && isPrime(ascii[i])){
                  prime=true;
                  putchar(i);
            }
          本來把"字元出現次數"歸零的工作
          ，是放在下面，不過我想在這邊順便
          歸零，於在這邊是加入這段
                mascii[i]=0;

        ，然後把下面綠色的拿掉。結果我自己試
         ok，送出去又不行了...看起來從if後面把ascii[*]
        歸零都可以啊
         }

         //若沒有出現次數為質數的字元，印出empty
         if(!prime)
            cout<<"empty";
         putchar('\n');

         prime=false;


         //字元出現次數歸零
         for(int i=48;i<ASCII_PRINTABLE_MAX;i++)
            ascii[i]=0;

      }


完整+色彩標示的code

http://costbook.googlepages.com/10789-3_cpp.html



※ 引述《ledia (contemplation)》之銘言：
: ※ 引述《costbook (CB)》之銘言：
: :    char ascii[ASCII_PRINTABLE_MAX];
:   如果出現次數大於 128, 甚至 256
:   用一個 char/unsigned char 就計不下了
:   所以你 2001 剛好是對的真的運氣很好
:   我用 1999 測, 你的程式就錯啦 :p
:   我以前也死在這種小地方過 Orz
:   重點就是多測點測資, 看看有沒有異常囉

--
年度6大搞笑發言

同學A：機械式鍵盤耶，好爛喔...  │同學D：這是個4對16的多工器        
同學B：腳踏車也有碟煞喔，騙誰...│同學E：我要寫遊戲外掛             
同學C：iPod的音質很好           │同學F：C++除了class，根本就和C一樣

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.139.153.131
→ costbook:1ACM online judge的系統真的怪怪的...
→ costbook:我把這三行宣告的順序換了一下
→ costbook:      int count=0;
→ costbook:      bool prime=false;
→ costbook:      char in;
→ costbook:就出現runtime error，換回來又好了...
→ costbook:不過歸零的問題還是搞不懂
推 ledia:如果我沒算錯的話, 你新的 code, ascii 只有 126 格
→ ledia:但是 ASCII_PRINTABLE_MAX 是 127
→ ledia:因此你歸零會歸到 ascii[126] 這是會出問題的
→ ledia:run-time error 或 wrong answer 可能因此而來
→ ledia:對了, 寫到第 ascii[126] 時, 就是寫到之前的 stack var
→ ledia:也就是 in, prime 那些變數
→ ledia:這次我只用看的, 沒測過, 有沒有別的問題我就不知道了
推 costbook:對耶...謝啦   (不過只快了0.001秒...)
推 ledia:這個加不了多快的...
→ ledia:要加快的話, 我建議把 prime 先算好存在 table 裡...
→ ledia:最一開始一次算出來, 以後怎麼查都是一次 table-lookuup
→ ledia:isPrime 才應該是瓶頸處
→ ledia:然後, 分三段 for 可能可以減少一點時間.. 也可能減不了
→ ledia:不過至少少 process 一些不可能出現的字元
→ ledia:歸零也不需要每個都歸, ascii[i]>0 和 isPrime 拆開
→ ledia:ascii[i] > 0 時才需要歸零
→ ledia:想到的大概就這些.. 再麻煩一點的.. 就懶得想了 XD
推 costbook:好方法，來試試看
推 costbook:結果：時間一樣，記憶體用量變大.可能試測資太小，
→ costbook:所以看不出效果....算了，去研究下一題了
↑我自己發文的...我幹嘛用推文回啊
※ 編輯: costbook        來自: 220.139.153.131      (07/03 21:48)
推 drkkimo:= =...|||