Beyond the Void

项目地址 http://code.google.com/p/vakuum-oj/

简介

Vakuum是一个基于Linux+PHP的在线评测系统（Online Judge），主要面向信息学竞赛（OI）和ACM/ICPC。

功能

在线评测

用户提交程序代码，在线编译，执行测试数据，对其评判并返回结果。支持自定义检查器(Speciel Judge)。支持特殊类型题目（代码检查、交互式、库式、提交答案式）。

比赛举办

兼顾OI和ACM，支持个人赛、团队赛。比赛模式有在线赛（ACM），离线赛（OI），自由计时赛（USACO）。

晋级模式

根据现有题库，由管理员设置或用户推荐一组晋级路线，即做完一组题目后才能进入下一组，并获得相应称号。参加USACO和UVA。

问题讨论

简洁、高效、可控。

其他功能

题库检索，用户排名，队伍系统，权限管理，代码备份，……

架构

Vakuum 系统分为vakuum-web和vakuum-judge两大模块。vakuum-web是一个在线评测系统界面，需要PHP和MySQL支持，可以建立 在Linux或Windows平台下。vakuum-judge是评测系统的核心模块，负责处理用户评测请求，与vakuum-web进行通信。通信模块 为PHP，核心由C语言编写，只能运行在Linux(Unix)平台下。

vakuum-web是基 于PHP和MySQL的一个B/S应用程序，采用MVC（模型-视图-控制器）架构设计，负责与用户交互和与核心通信。支持于评测机分离或和一，支持多评 测机协同作业，不需要daemon和底层权限。用户通过访问vakuum-web查看题目，提交代码，vakuum-web将请求派发给vakuum- judge终端。支持多评测机数据同步，支持测试数据分发管理。主要采用HTTP信道发送命令，FTP信道发送数据。

vakuum- judge通信模块由PHP编写，收到请求以后，使用C语言编写的核心对代码进行编译，并在执行器沙盒中执行，保证系统安全。执行器使用ptrace监控 用户程序的系统调用和文件调用，根据需求加以放行或禁止，同时支持内存峰值统计，内存限制，用户时间统计，时间限制，输出文件大小限制。

现状

正在开发，vakuum-judge核心部分基本完成，vakuum-web底层架构设计完成，正在完善功能。现需要对PHP熟悉的开发者，善于网页设计和美化的开发者，精通Linux系统编程的开发者，有意将内核移植到Windows的开发者，欢迎有意者加入开发。

现在我正处在2008年和2009年的交界处，在这个时刻，回望2008，展望2009，是最合适不过的了。

想一想2008年，我的大事都是围绕OI展开的，一月 冬令营，二月 新年，三月 COGS，四月 省选，五月 APIO和CTSC，六月 省选加试，七月 省队培训，八月 NOI，九月 参悟动态规划，十月 NOIP模拟，十一月 NOIP2008，十二月 POI。

也许在今后的日子中，没有一年会像今年一样，我在整个一年中把很大部分的精力投入到信息学竞赛中，不妨就称2008年为“OI年”吧。

2008年就匆匆地过去了，这一年来我变化了很多。我变得关心这个世界了，现在我十分关注从前很少的阅读新闻时评。我变得稳重了，很少再会因为一些小事而心情大起大落。我变得务实了，做事前我会充分地考虑实际情况。我变得大胆了，敢于为“天下先”，哪怕会遭到被人排斥。

2009年已经向我走来。2009年，将是我走向成熟的一年。到了2009年底，我就18岁了，我将成为一般意义上的一个成人。我要学会独立生存，学会为自己负责，学会承受压力。2009年，将会是我告别OI的一年，相信我一定会在NOI2009中以辉煌的成绩结束我的OI生涯。

2009，我已经准备好了。

OI生涯结束……在逸夫楼那些的日子里

终于，结束了，我的OI生涯…………

什么都不想说，因为没有成功，

我不想说原因，因为有太多太多无奈……

这世界本就不是平等的，所以………

两年，玩过，学过，笑过，苦过……

一万多行程序，其实不算很多………………

也许那句话说的对，毕竟经历过…………

从高一满满一机房50、60+人减少到10个人……

我想，我们坚持下来了…………

而缺少的，只不过是一张奖状…………

有同学曾问我，没拿到奖岂不是白费一场力气…………

也许同学是对的，但我，不想放弃…………

一如既往地坚持，没有老师的辅导…………

我们06级非特招生的命运…………

我想，逸夫的三楼从未属于过我们…………

最快乐的，是在二楼的那些日子……

liyao、Francis、Maylaya、zxc111、privateeye、elsyin，祝你们好运。

EMBER、Nickname、当然还有我WaterFire，我们一起努力文化课。

开封的小子Isis，等着你的好消息。

未知的高考，还等待我…………

Challenge Fail But Chance Still………………

接下来的日子…………

青灯、书卷、浓茶…………

然后是…………

面包、牛奶…………

有挑战，才会有激情！

失败，嘲笑不倒真正的勇士。

困难，恐吓不了无畏的斗士。

人生，我与你不死不休！

————谨以此文纪念我的OI生涯并献给奋斗在逸夫楼里的同学们

又是一年联赛时，有人欢喜有人忧。这是一位英雄绝笔，这是失败得离开OI。我不再做什么评论，谨以此劝诫高一高二的同学们一定要继续努力，失败毕竟不会永远是偶然的。

NOI2008已经谢幕，没有进入省队的我又以夏令营铜牌的成绩悻悻而归。暑假已经过去，高二已经来了，OI的日子还会长吗？

尽管我是一个从初中开始的OIER，但去年这个时候，我才正式步入OI殿堂。而现在，我已经距离开OI不远了，只有一年。只有一年，我这一年任务很重，继续往上的OI之路很艰难。

明天开始正式上课，我要把握好高二。

NOI在即，我还不会Treap，这是一件多么恐怖的事情啊。今天下午在iRachex大牛的指导下，我学了Treap。不能算是会了，只是初窥门径而已。

开始看了许多介绍文章，还被误导了。因为有人用最大堆，有人用最小堆，我被迷惑了。还有就是左旋和右旋，有的人正好认识相反，我恰好看着两篇认识相反的文章在学习。

总结一下Treap

插入：
按BST基本性质插入，生成修正值(有人叫优先级、附加值、堆权值)，并按照最大堆序维护修正码。
向左子树插入返回后
如果左子修正值大于根修正值，堆序被破坏，将根旋转到右子树（右旋）
向右子树插入返回后
如果右子修正值大于根修正值，堆序被破坏，将根旋转到左子树（左旋）

删除：
叶节点：直接删除
链节点：链接上子节点并删除
完全节点：
若其左子树修正值较小，将该节点左旋，递归删除左节点
若其右子树修正值较小，将该节点左旋，递归删除右节点

左旋：将根X旋转到左子树

Y=X右子
X右子=Y左子
Y左子=X
X=Y

右旋：将根X旋转到右子树

Y=X左子
X左子=Y右子
Y右子=X
X=Y

一个非常棒的Treap演示
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Treap-Example.htm

附一段第一次写的Treap代码
#include
#include
#define MAX 100

int i;
for (i=3;i>=1;i--)
T.insert(T.root,i);
T.print(T.root);
for (i=3;i>=1;i--)
{
cout << endl;
T.remove(T.root,i);
T.print(T.root);
}
return 0;
}