// author: Leonardone @ NEETSDKASU
import java.util.*;
import java.lang.*;
import java.io.*;
import java.nio.*;
class Ideone
{
{
final int TEST = 50000;
doIt(TEST, 10);
doIt(TEST, 8);
doIt(TEST, 5);
}
static void doIt(final int TEST, final int SIZEBIT) {
System.
out.
println(":::::::::::::::::::::"); System.
out.
println("TEST COUNT: " + TEST
); System.
out.
println("SIZEBIT: " + SIZEBIT
); System.
out.
println("SIZE: " + (1 << SIZEBIT
));
testFoo(TEST, SIZEBIT);
testArrayList(TEST, SIZEBIT);
testIntBuffer(TEST, SIZEBIT);
testArray(TEST, SIZEBIT);
}
static void testFoo(final int TEST, final int SIZEBIT) {
Foo foo = new Foo(SIZEBIT);
long t0, t1;
int sum;
for (int i = 0; i < TEST; i++) {
foo.put(i, i * 2);
}
System.
out.
println("foo addNew time: " + (t1
- t0
));
for (int i = 0; i < TEST; i++) {
foo.put(i, foo.get(i) * 3);
}
System.
out.
println("foo update time: " + (t1
- t0
));
sum = 0;
for (int i = 0; i < TEST; i++) {
sum += foo.get(i);
}
System.
out.
println("foo get time: " + (t1
- t0
)); System.
out.
println("foo sum: " + sum
); }
static void testArrayList(final int TEST, final int SIZEBIT) {
ArrayList<Integer> list = new ArrayList<>(1 << SIZEBIT);
long t0, t1;
int sum;
for (int i = 0; i < TEST; i++) {
list.add(i * 2);
}
System.
out.
println("list addNew time: " + (t1
- t0
));
for (int i = 0; i < TEST; i++) {
list.set(i, list.get(i) * 3);
}
System.
out.
println("list update time: " + (t1
- t0
));
sum = 0;
for (int i = 0; i < TEST; i++) {
sum += list.get(i);
}
System.
out.
println("list get time: " + (t1
- t0
)); System.
out.
println("list sum: " + sum
); }
static void testIntBuffer(final int TEST, final int SIZEBIT) {
IntBuffer ib = IntBuffer.allocate(1 << SIZEBIT);
long t0, t1;
int sum;
for (int i = 0; i < TEST; i++) {
if (i >= ib.limit()) {
ib
= IntBuffer.
wrap(Arrays.
copyOf(ib.
array(), ib.
limit() + (1 << SIZEBIT
))); }
ib.put(i, i * 2);
}
System.
out.
println("buffer addNew time: " + (t1
- t0
));
for (int i = 0; i < TEST; i++) {
ib.put(i, ib.get(i) * 3);
}
System.
out.
println("buffer update time: " + (t1
- t0
));
sum = 0;
for (int i = 0; i < TEST; i++) {
sum += ib.get(i);
}
System.
out.
println("buffer get time: " + (t1
- t0
)); System.
out.
println("buffer sum: " + sum
); }
static void testArray(final int TEST, final int SIZEBIT) {
int[] ia = new int[1 << SIZEBIT];
long t0, t1;
int sum;
for (int i = 0; i < TEST; i++) {
if (i >= ia.length) {
ia
= (Arrays.
copyOf(ia, ia.
length + (1 << SIZEBIT
))); }
ia[i] = i * 2;
}
System.
out.
println("array addNew time: " + (t1
- t0
));
for (int i = 0; i < TEST; i++) {
ia[i] = ia[i] * 3;
}
System.
out.
println("array update time: " + (t1
- t0
));
sum = 0;
for (int i = 0; i < TEST; i++) {
sum += ia[i];
}
System.
out.
println("array get time: " + (t1
- t0
)); System.
out.
println("array sum: " + sum
);
}
static class Foo
{
int size, mask, bit;
int[][] buf;
public Foo(int bit) {
this.bit = bit;
size = 1 << (bit & 0xF);
mask = size - 1;
buf = new int[1][];
buf[0] = new int[size];
}
public void put(int index, int value) {
int y = index >> bit;
if (y >= buf.length) {
buf
= Arrays.
copyOf(buf, y
+ 1); }
if (buf[y] == null) {
buf[y] = new int[size];
}
buf[y][index & mask] = value;
}
public int get(int index) {
int y = index >> bit;
if (y < buf.length) {
if (buf[y] != null) {
return buf[y][index & mask];
}
}
return 0;
}
}
}
Ly8gYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLm5pby4qOwoKY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWZpbmFsIGludCBURVNUID0gNTAwMDA7CgkJCgkJZG9JdChURVNULCAxMCk7CgkJZG9JdChURVNULCA4KTsKCQlkb0l0KFRFU1QsIDUpOwoJCQoJfQoJCglzdGF0aWMgdm9pZCBkb0l0KGZpbmFsIGludCBURVNULCBmaW5hbCBpbnQgU0laRUJJVCkgewoJCQoJCVN5c3RlbS5vdXQucHJpbnRsbigiOjo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Iik7CgkJU3lzdGVtLm91dC5wcmludGxuKCJURVNUIENPVU5UOiAiICsgVEVTVCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJTSVpFQklUOiAiICsgU0laRUJJVCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJTSVpFOiAiICsgKDEgPDwgU0laRUJJVCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCQkKCQl0ZXN0Rm9vKFRFU1QsIFNJWkVCSVQpOwoJCXRlc3RBcnJheUxpc3QoVEVTVCwgU0laRUJJVCk7CgkJdGVzdEludEJ1ZmZlcihURVNULCBTSVpFQklUKTsKCQl0ZXN0QXJyYXkoVEVTVCwgU0laRUJJVCk7Cgl9CgkKCXN0YXRpYyB2b2lkIHRlc3RGb28oZmluYWwgaW50IFRFU1QsIGZpbmFsIGludCBTSVpFQklUKSB7CgkJRm9vIGZvbyA9IG5ldyBGb28oU0laRUJJVCk7CgkJbG9uZyB0MCwgdDE7CgkJaW50IHN1bTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlmb28ucHV0KGksIGkgKiAyKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImZvbyBhZGROZXcgdGltZTogICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCWZvby5wdXQoaSwgZm9vLmdldChpKSAqIDMpOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiZm9vIHVwZGF0ZSB0aW1lOiAgICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7CgkJCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlzdW0gPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCXN1bSArPSBmb28uZ2V0KGkpOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiZm9vIGdldCB0aW1lOiAgICAgICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImZvbyBzdW06ICAgICAgICAgICAgIiArIHN1bSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoJfQoJCglzdGF0aWMgdm9pZCB0ZXN0QXJyYXlMaXN0KGZpbmFsIGludCBURVNULCBmaW5hbCBpbnQgU0laRUJJVCkgewoJCUFycmF5TGlzdDxJbnRlZ2VyPiBsaXN0ID0gbmV3IEFycmF5TGlzdDw+KDEgPDwgU0laRUJJVCk7CgkJbG9uZyB0MCwgdDE7CgkJaW50IHN1bTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlsaXN0LmFkZChpICogMik7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJsaXN0IGFkZE5ldyB0aW1lOiAgICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlsaXN0LnNldChpLCBsaXN0LmdldChpKSAqIDMpOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigibGlzdCB1cGRhdGUgdGltZTogICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7CgkJCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlzdW0gPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCXN1bSArPSBsaXN0LmdldChpKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImxpc3QgZ2V0IHRpbWU6ICAgICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJsaXN0IHN1bTogICAgICAgICAgICIgKyBzdW0pOwkJCgkJU3lzdGVtLm91dC5mbHVzaCgpOwoJfQoKCXN0YXRpYyB2b2lkIHRlc3RJbnRCdWZmZXIoZmluYWwgaW50IFRFU1QsIGZpbmFsIGludCBTSVpFQklUKSB7CgkJSW50QnVmZmVyIGliID0gSW50QnVmZmVyLmFsbG9jYXRlKDEgPDwgU0laRUJJVCk7CgkJbG9uZyB0MCwgdDE7CgkJaW50IHN1bTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlpZiAoaSA+PSBpYi5saW1pdCgpKSB7CgkJCQlpYiA9IEludEJ1ZmZlci53cmFwKEFycmF5cy5jb3B5T2YoaWIuYXJyYXkoKSwgaWIubGltaXQoKSArICgxIDw8IFNJWkVCSVQpKSk7CgkJCX0KCQkJaWIucHV0KGksIGkgKiAyKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImJ1ZmZlciBhZGROZXcgdGltZTogIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCWliLnB1dChpLCBpYi5nZXQoaSkgKiAzKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImJ1ZmZlciB1cGRhdGUgdGltZTogIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoJCQoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJc3VtID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlzdW0gKz0gaWIuZ2V0KGkpOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiYnVmZmVyIGdldCB0aW1lOiAgICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImJ1ZmZlciBzdW06ICAgICAgICAgIiArIHN1bSk7CQoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCX0KCQkKCXN0YXRpYyB2b2lkIHRlc3RBcnJheShmaW5hbCBpbnQgVEVTVCwgZmluYWwgaW50IFNJWkVCSVQpIHsKCQlpbnRbXSBpYSA9IG5ldyBpbnRbMSA8PCBTSVpFQklUXTsKCQlsb25nIHQwLCB0MTsKCQlpbnQgc3VtOwoKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCWlmIChpID49IGlhLmxlbmd0aCkgewoJCQkJaWEgPSAoQXJyYXlzLmNvcHlPZihpYSwgaWEubGVuZ3RoICsgKDEgPDwgU0laRUJJVCkpKTsKCQkJfQoJCQlpYVtpXSA9IGkgKiAyOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiYXJyYXkgYWRkTmV3IHRpbWU6ICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7CgoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJaWFbaV0gPSBpYVtpXSAqIDM7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJhcnJheSB1cGRhdGUgdGltZTogICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCQkKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCXN1bSA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJc3VtICs9IGlhW2ldOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiYXJyYXkgZ2V0IHRpbWU6ICAgICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImFycmF5IHN1bTogICAgICAgICAgIiArIHN1bSk7CQoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCgl9CgkKCXN0YXRpYyBjbGFzcyBGb28KCXsKCQlpbnQgc2l6ZSwgbWFzaywgYml0OwoJCWludFtdW10gYnVmOwoJCXB1YmxpYyBGb28oaW50IGJpdCkgewoJCQl0aGlzLmJpdCA9IGJpdDsKCQkJc2l6ZSA9IDEgPDwgKGJpdCAmIDB4Rik7CgkJCW1hc2sgPSBzaXplIC0gMTsKCQkJYnVmID0gbmV3IGludFsxXVtdOwoJCQlidWZbMF0gPSBuZXcgaW50W3NpemVdOwoJCX0KCQlwdWJsaWMgdm9pZCBwdXQoaW50IGluZGV4LCBpbnQgdmFsdWUpIHsKCQkJaW50IHkgPSBpbmRleCA+PiBiaXQ7CgkJCWlmICh5ID49IGJ1Zi5sZW5ndGgpIHsKCQkJCWJ1ZiA9IEFycmF5cy5jb3B5T2YoYnVmLCB5ICsgMSk7CgkJCX0KCQkJaWYgKGJ1Zlt5XSA9PSBudWxsKSB7CgkJCQlidWZbeV0gPSBuZXcgaW50W3NpemVdOwoJCQl9CgkJCWJ1Zlt5XVtpbmRleCAmIG1hc2tdID0gdmFsdWU7CgkJfQoJCXB1YmxpYyBpbnQgZ2V0KGludCBpbmRleCkgewoJCQlpbnQgeSA9IGluZGV4ID4+IGJpdDsKCQkJaWYgKHkgPCBidWYubGVuZ3RoKSB7CgkJCQlpZiAoYnVmW3ldICE9IG51bGwpIHsKCQkJCQlyZXR1cm4gYnVmW3ldW2luZGV4ICYgbWFza107CgkJCQl9CgkJCX0KCQkJcmV0dXJuIDA7CgkJfQoJfQp9