竹園論壇

標題: [IOICAMP2015][NPSC2014][Treap] b379 蚯蚯(扭) [打印本頁]

作者: Sylveon 時間: 2015-2-12 15:58
標題: [IOICAMP2015][NPSC2014][Treap] b379 蚯蚯(扭)
原題：http://zerojudge.tw/ShowProblem?problemid=b379
NPSC：http://contest.cc.ntu.edu.tw/npsc2014/default.asp
IOICAMP：http://judge.ioicamp.org/problems/33

AC：http://zerojudge.tw/Submissions?problemid=b379&account=lfs92002

又被ZJ不能用C++11給雷到ORZ，就實作一個「可持久化」Persistent data structure(WIKI)資料結構來處理，在這裡實作的是可持久就化Treap。原本有做垃圾回收，但是IOICAMP上時間較緊，會導致TLE，ZJ又不支援C++11的shared_ptr，然後就一點用處也沒有......

每次Treap的Rand都爆炸，從網路學了新的Rand來用就AC了~

Rand

[C++] 純文本查看 復制代碼

inline int ran(){

        static int x=15180255;

        return x=(x*0xdefaced+1)&INT_MAX;

}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)