Monkey 和 Kangroo还会回来吗
ultmaster edited 6 年,9 月前
膜 LOJ。以及抄袭原文。
# | Language | Loop | Euler Sieve | Floyd-Warshall | std::set |
Memory Alloc (new) |
---|---|---|---|---|---|---|
Codeforces | G++ 5.1.0 (-O2) | 288 | 295 | 967 | 701 | 857 |
LibreOJ(2017.12.10) | G++ 5.4.0 (-O2) | 301 | 319 | 823 | 850 | 736 |
Universal Online Judge | G++ 4.8.4 (-O2) | 435 | 530 | 1377 | 996 | 918 |
BZOJ | G++ 4.4.5 (-O2) | 504 | 1280 | 2092 | 1368 | 1568 |
HUSTOJ | G++ 4.4.5 (-O2) | 908 | 1460 | 1413 | 1553 | Unexpected MLE (ML = 512MB) |
EOJ (Goat) | G++ 5.4.0 (-O2) | 464 | 344 | 1120 | 672 | 736 (ML = 1GB) |
EOJ (Cow) | G++ 5.4.0 (-O2) | 332 | 388 | 1056 | 736 | 768 (ML = 1GB) |
It seems that EOJ is a little bit slower than Codeforces, but fast enough.
// Test 1: Loop
#include<cstdio>
using namespace std;
int main(){
int a=1000000000,b=1;
while(a)b<<=1,a--;
printf("%d\n",b);
return 0;
}
// Test 2: Euler Sieve
#include<cstdio>
using namespace std;
const int MX=50000000;
int p[MX],m[MX],pc;
int main(){
for(int i=2;i<MX;i++){
if(!m[i])p[++pc]=m[i]=i;
static int k;
for(int j=1;j<=pc&&p[j]<=m[i]&&(k=p[j]*i)<MX;j++)m[k]=p[j];
}
int ans=0;
for(int i=1;i<=pc;i++)ans^=p[i];
printf("%d\n",ans);
return 0;
}
// Test 3: Floyd-Warshall
#include<cstdio>
using namespace std;
const int MX=1000;
int G[MX][MX];
int sed=0;
inline int rand(){return sed=(sed*sed*73+sed*233+19260817)&0x0000ffff;}
int main(){
for(int i=0;i<MX;i++)
for(int j=0;j<MX;j++)
G[i][j]=rand();
for(int i=0;i<MX;i++)
for(int j=0;j<MX;j++)
for(int k=0;k<MX;k++)
if(G[j][k]>G[j][i]+G[i][k])G[j][k]=G[j][i]+G[i][k];
int ans=0;
for(int i=0;i<MX;i++)
for(int j=0;j<MX;j++)
ans^=G[i][j];
printf("%d\n",ans);
return 0;
}
// Test 4: std::set
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int MX=1000000;
int sed=0;
inline int rand(){return sed=(sed*sed*73+sed*233+19260817);}
int main(){
set<int>S;
for(int i=0;i<MX;i++)S.insert(rand());
int ans=0;
for(set<int>::iterator it=S.begin();it!=S.end();it++)ans^=*it;
printf("%d\n",ans);
return 0;
}
// Test 5: Memory Alloc (new)
#include<cstdio>
using namespace std;
const int MX=20000000;
int *it[MX];
int main(){
for(int i=0;i<MX;i++)it[i]=new int;
for(int i=0;i<MX;i++)*it[i]=i;
int ans=0;
for(int i=0;i<MX;i++)ans^=*it[i];
printf("%d\n",ans);
return 0;
}
3 million non-negative integers in one single line.
Input will be faster if it is naturally buffered (for example in Python).
Time limit is 5 seconds. All numbers are in millisecond(s).
# | Machine | $[0,2)$ | $[0,8)$ | $[0,2^{15})$ | $[0,2^{31})$ | $[0,2^{63})$ |
---|---|---|---|---|---|---|
fread |
Goat | 20 | 12 | 52 | 72 | 120 |
fread |
Cow | 16 | 12 | 48 | 88 | 104 |
getchar |
Goat | 64 | 52 | 140 | 252 | 452 |
getchar |
Cow | 60 | 68 | 160 | 268 | 520 |
cin.tie(0) |
Goat | 460 | 560 | 764 | 1344 | 2044 |
cin.tie(0) |
Cow | 464 | 696 | 948 | 1344 | 3096 |
scanf |
Goat | 288 | 252 | 444 | 600 | 844 |
scanf |
Cow | 256 | 260 | 572 | 516 | 1148 |
cin |
Goat | 516 | 608 | 848 | 1340 | 2100 |
cin |
Cow | 514 | 516 | 860 | 1444 | 2456 |
Java | Goat | 2732 | 3016 | 3368 | 3928 | 4440 |
Java | Cow | 2572 | 2904 | 3184 | 4396 | TL |
Java Buffered | Goat | 780 | 900 | 996 | 916 | 1864 |
Java Buffered | Cow | 652 | 620 | 836 | 1220 | 1472 |
Python | Goat | 836 | 992 | 1052 | 1052 | 1072 |
Python | Cow | 984 | 616 | 672 | 812 | 948 |
No