// author: Leonardone @ NEETSDKASU
import java.util.*;
import java.lang.*;
import java.io.*;
import java.nio.*;
class Ideone
{
{
final int TEST = 500000;
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] *= 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;
}
}
}
Ly8gYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLm5pby4qOwoKY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWZpbmFsIGludCBURVNUID0gNTAwMDAwOwoJCQoJCWRvSXQoVEVTVCwgMTApOwoJCWRvSXQoVEVTVCwgOCk7CgkJZG9JdChURVNULCA1KTsKCQkKCX0KCQoJc3RhdGljIHZvaWQgZG9JdChmaW5hbCBpbnQgVEVTVCwgZmluYWwgaW50IFNJWkVCSVQpIHsKCQkKCQlTeXN0ZW0ub3V0LnByaW50bG4oIjo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6OiIpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiVEVTVCBDT1VOVDogIiArIFRFU1QpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiU0laRUJJVDogIiArIFNJWkVCSVQpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiU0laRTogIiArICgxIDw8IFNJWkVCSVQpKTsKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7CgkJCgkJdGVzdEZvbyhURVNULCBTSVpFQklUKTsKCQl0ZXN0QXJyYXlMaXN0KFRFU1QsIFNJWkVCSVQpOwoJCXRlc3RJbnRCdWZmZXIoVEVTVCwgU0laRUJJVCk7CgkJdGVzdEFycmF5KFRFU1QsIFNJWkVCSVQpOwoJfQoJCglzdGF0aWMgdm9pZCB0ZXN0Rm9vKGZpbmFsIGludCBURVNULCBmaW5hbCBpbnQgU0laRUJJVCkgewoJCUZvbyBmb28gPSBuZXcgRm9vKFNJWkVCSVQpOwoJCWxvbmcgdDAsIHQxOwoJCWludCBzdW07CgoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJZm9vLnB1dChpLCBpICogMik7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJmb28gYWRkTmV3IHRpbWU6ICAgICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlmb28ucHV0KGksIGZvby5nZXQoaSkgKiAzKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImZvbyB1cGRhdGUgdGltZTogICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoJCQoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJc3VtID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlzdW0gKz0gZm9vLmdldChpKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImZvbyBnZXQgdGltZTogICAgICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJmb28gc3VtOiAgICAgICAgICAgICIgKyBzdW0pOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCX0KCQoJc3RhdGljIHZvaWQgdGVzdEFycmF5TGlzdChmaW5hbCBpbnQgVEVTVCwgZmluYWwgaW50IFNJWkVCSVQpIHsKCQlBcnJheUxpc3Q8SW50ZWdlcj4gbGlzdCA9IG5ldyBBcnJheUxpc3Q8PigxIDw8IFNJWkVCSVQpOwoJCWxvbmcgdDAsIHQxOwoJCWludCBzdW07CgoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJbGlzdC5hZGQoaSAqIDIpOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigibGlzdCBhZGROZXcgdGltZTogICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7CgoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJbGlzdC5zZXQoaSwgbGlzdC5nZXQoaSkgKiAzKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImxpc3QgdXBkYXRlIHRpbWU6ICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoJCQoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJc3VtID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlzdW0gKz0gbGlzdC5nZXQoaSk7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJsaXN0IGdldCB0aW1lOiAgICAgICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigibGlzdCBzdW06ICAgICAgICAgICAiICsgc3VtKTsJCQoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCX0KCglzdGF0aWMgdm9pZCB0ZXN0SW50QnVmZmVyKGZpbmFsIGludCBURVNULCBmaW5hbCBpbnQgU0laRUJJVCkgewoJCUludEJ1ZmZlciBpYiA9IEludEJ1ZmZlci5hbGxvY2F0ZSgxIDw8IFNJWkVCSVQpOwoJCWxvbmcgdDAsIHQxOwoJCWludCBzdW07CgoJCXQwID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJaWYgKGkgPj0gaWIubGltaXQoKSkgewoJCQkJaWIgPSBJbnRCdWZmZXIud3JhcChBcnJheXMuY29weU9mKGliLmFycmF5KCksIGliLmxpbWl0KCkgKyAoMSA8PCBTSVpFQklUKSkpOwoJCQl9CgkJCWliLnB1dChpLCBpICogMik7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJidWZmZXIgYWRkTmV3IHRpbWU6ICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlpYi5wdXQoaSwgaWIuZ2V0KGkpICogMyk7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJidWZmZXIgdXBkYXRlIHRpbWU6ICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCQkKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCXN1bSA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJc3VtICs9IGliLmdldChpKTsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImJ1ZmZlciBnZXQgdGltZTogICAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJidWZmZXIgc3VtOiAgICAgICAgICIgKyBzdW0pOwkKCQlTeXN0ZW0ub3V0LmZsdXNoKCk7Cgl9CgkJCglzdGF0aWMgdm9pZCB0ZXN0QXJyYXkoZmluYWwgaW50IFRFU1QsIGZpbmFsIGludCBTSVpFQklUKSB7CgkJaW50W10gaWEgPSBuZXcgaW50WzEgPDwgU0laRUJJVF07CgkJbG9uZyB0MCwgdDE7CgkJaW50IHN1bTsKCgkJdDAgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IFRFU1Q7IGkrKykgewoJCQlpZiAoaSA+PSBpYS5sZW5ndGgpIHsKCQkJCWlhID0gKEFycmF5cy5jb3B5T2YoaWEsIGlhLmxlbmd0aCArICgxIDw8IFNJWkVCSVQpKSk7CgkJCX0KCQkJaWFbaV0gPSBpICogMjsKCQl9CgkJdDEgPSBTeXN0ZW0ubmFub1RpbWUoKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImFycmF5IGFkZE5ldyB0aW1lOiAgIiArICh0MSAtIHQwKSk7CgkJU3lzdGVtLm91dC5mbHVzaCgpOwoKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgVEVTVDsgaSsrKSB7CgkJCWlhW2ldICo9IDM7CgkJfQoJCXQxID0gU3lzdGVtLm5hbm9UaW1lKCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJhcnJheSB1cGRhdGUgdGltZTogICIgKyAodDEgLSB0MCkpOwoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCQkKCQl0MCA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCXN1bSA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBURVNUOyBpKyspIHsKCQkJc3VtICs9IGlhW2ldOwoJCX0KCQl0MSA9IFN5c3RlbS5uYW5vVGltZSgpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiYXJyYXkgZ2V0IHRpbWU6ICAgICAiICsgKHQxIC0gdDApKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImFycmF5IHN1bTogICAgICAgICAgIiArIHN1bSk7CQoJCVN5c3RlbS5vdXQuZmx1c2goKTsKCgl9CgkKCXN0YXRpYyBjbGFzcyBGb28KCXsKCQlpbnQgc2l6ZSwgbWFzaywgYml0OwoJCWludFtdW10gYnVmOwoJCXB1YmxpYyBGb28oaW50IGJpdCkgewoJCQl0aGlzLmJpdCA9IGJpdDsKCQkJc2l6ZSA9IDEgPDwgKGJpdCAmIDB4Rik7CgkJCW1hc2sgPSBzaXplIC0gMTsKCQkJYnVmID0gbmV3IGludFsxXVtdOwoJCQlidWZbMF0gPSBuZXcgaW50W3NpemVdOwoJCX0KCQlwdWJsaWMgdm9pZCBwdXQoaW50IGluZGV4LCBpbnQgdmFsdWUpIHsKCQkJaW50IHkgPSBpbmRleCA+PiBiaXQ7CgkJCWlmICh5ID49IGJ1Zi5sZW5ndGgpIHsKCQkJCWJ1ZiA9IEFycmF5cy5jb3B5T2YoYnVmLCB5ICsgMSk7CgkJCX0KCQkJaWYgKGJ1Zlt5XSA9PSBudWxsKSB7CgkJCQlidWZbeV0gPSBuZXcgaW50W3NpemVdOwoJCQl9CgkJCWJ1Zlt5XVtpbmRleCAmIG1hc2tdID0gdmFsdWU7CgkJfQoJCXB1YmxpYyBpbnQgZ2V0KGludCBpbmRleCkgewoJCQlpbnQgeSA9IGluZGV4ID4+IGJpdDsKCQkJaWYgKHkgPCBidWYubGVuZ3RoKSB7CgkJCQlpZiAoYnVmW3ldICE9IG51bGwpIHsKCQkJCQlyZXR1cm4gYnVmW3ldW2luZGV4ICYgbWFza107CgkJCQl9CgkJCX0KCQkJcmV0dXJuIDA7CgkJfQoJfQp9