// compile with
// g++-4.8 -o main_gcc -O3 -std=c++11 -Wall -Wextra -pedantic -Werror main.cpp square.cpp
// clang++ -o main_clang -O3 -std=c++11 -Wall -Wextra -pedantic -Werror main.cpp square.cpp
#include <algorithm>
#include <ctime>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> Vec;
//int n = 8;
int n = 1000000;
size_t max_print = 10;
int shift = 3;
int runs = 400;
void shift_rev( Vec& v, size_t a )
{
reverse( v.begin(), v.end() );
reverse( v.begin(), v.begin() + a );
reverse( v.begin() + a, v.end() );
}
void shift_swap(Vec& v, size_t a)
{
size_t max_s = v.size() / a;
for( size_t s = 1; s < max_s; ++s )
for( size_t i = 0; i < a; ++i )
swap( v[i], v[s*a+i] );
for( size_t i = 0; i < a; ++i )
swap( v[i], v[(max_s*a+i) % v.size()] );
}
void print(const Vec& v)
{
copy( v.begin(), v.end(), ostream_iterator<int>( cout, ",") );
cout << endl;
}
void test( Vec v, function<void(Vec&, size_t)> f, const string& name )
{
unsigned int startTime = clock();
for ( int i = 0; i < runs; ++i )
f( v, shift % v.size() );
// sum the result to prevent the optimizer from removing everything.
auto check = accumulate( v.begin(), v.end(), 0 );
if ( v.size() <= max_print )
print( v );
double duration = static_cast<double>(clock() - startTime) / CLOCKS_PER_SEC;
cout << name << " (check: " << check << "), duration: " << duration << endl;
}
int main()
{
vector<int> v;
v.reserve( n );
for (int i = 1; i <= n; ++i )
v.push_back(i);
if ( v.size() <= max_print )
print( v );
test( v, &shift_rev, "rev " );
test( v, &shift_swap, "swap" );
}
Ly8gY29tcGlsZSB3aXRoCi8vIGcrKy00LjggLW8gbWFpbl9nY2MgLU8zIC1zdGQ9YysrMTEgLVdhbGwgLVdleHRyYSAtcGVkYW50aWMgLVdlcnJvciBtYWluLmNwcCBzcXVhcmUuY3BwCi8vIGNsYW5nKysgLW8gbWFpbl9jbGFuZyAtTzMgLXN0ZD1jKysxMSAtV2FsbCAtV2V4dHJhIC1wZWRhbnRpYyAtV2Vycm9yIG1haW4uY3BwIHNxdWFyZS5jcHAKCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHZlY3RvcjxpbnQ+IFZlYzsKLy9pbnQgbiA9IDg7CmludCBuID0gMTAwMDAwMDsKc2l6ZV90IG1heF9wcmludCA9IDEwOwppbnQgc2hpZnQgPSAzOwppbnQgcnVucyA9IDQwMDsKCnZvaWQgc2hpZnRfcmV2KCBWZWMmIHYsIHNpemVfdCBhICkKewoJcmV2ZXJzZSggdi5iZWdpbigpLCB2LmVuZCgpICk7CglyZXZlcnNlKCB2LmJlZ2luKCksIHYuYmVnaW4oKSArIGEgKTsKCXJldmVyc2UoIHYuYmVnaW4oKSArIGEsIHYuZW5kKCkgKTsKfQoKdm9pZCBzaGlmdF9zd2FwKFZlYyYgdiwgc2l6ZV90IGEpCnsKCXNpemVfdCBtYXhfcyA9IHYuc2l6ZSgpIC8gYTsKCWZvciggc2l6ZV90IHMgPSAxOyBzIDwgbWF4X3M7ICsrcyApCgkJZm9yKCBzaXplX3QgaSA9IDA7IGkgPCBhOyArK2kgKQoJCQlzd2FwKCB2W2ldLCB2W3MqYStpXSApOwoJZm9yKCBzaXplX3QgaSA9IDA7IGkgPCBhOyArK2kgKQoJCXN3YXAoIHZbaV0sIHZbKG1heF9zKmEraSkgJSB2LnNpemUoKV0gKTsKfQoKdm9pZCBwcmludChjb25zdCBWZWMmIHYpCnsKCWNvcHkoIHYuYmVnaW4oKSwgdi5lbmQoKSwgb3N0cmVhbV9pdGVyYXRvcjxpbnQ+KCBjb3V0LCAiLCIpICk7Cgljb3V0IDw8IGVuZGw7Cn0KCnZvaWQgdGVzdCggVmVjIHYsIGZ1bmN0aW9uPHZvaWQoVmVjJiwgc2l6ZV90KT4gZiwgY29uc3Qgc3RyaW5nJiBuYW1lICkKewoJdW5zaWduZWQgaW50IHN0YXJ0VGltZSA9IGNsb2NrKCk7CgoJZm9yICggaW50IGkgPSAwOyBpIDwgcnVuczsgKytpICkKCQlmKCB2LCBzaGlmdCAlIHYuc2l6ZSgpICk7CgoJLy8gc3VtIHRoZSByZXN1bHQgdG8gcHJldmVudCB0aGUgb3B0aW1pemVyIGZyb20gcmVtb3ZpbmcgZXZlcnl0aGluZy4KCWF1dG8gY2hlY2sgPSBhY2N1bXVsYXRlKCB2LmJlZ2luKCksIHYuZW5kKCksIDAgKTsKCglpZiAoIHYuc2l6ZSgpIDw9IG1heF9wcmludCApCgkJcHJpbnQoIHYgKTsKCiAgICBkb3VibGUgZHVyYXRpb24gPSBzdGF0aWNfY2FzdDxkb3VibGU+KGNsb2NrKCkgLSBzdGFydFRpbWUpIC8gQ0xPQ0tTX1BFUl9TRUM7CgoJY291dCA8PCBuYW1lIDw8ICIgKGNoZWNrOiAiIDw8IGNoZWNrIDw8ICIpLCBkdXJhdGlvbjogIiA8PCBkdXJhdGlvbiA8PCBlbmRsOwp9CgppbnQgbWFpbigpCnsKCXZlY3RvcjxpbnQ+IHY7Cgl2LnJlc2VydmUoIG4gKTsKCglmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kgKQoJCXYucHVzaF9iYWNrKGkpOwoKCWlmICggdi5zaXplKCkgPD0gbWF4X3ByaW50ICkKCQlwcmludCggdiApOwoKCXRlc3QoIHYsICZzaGlmdF9yZXYsICJyZXYgIiApOwoJdGVzdCggdiwgJnNoaWZ0X3N3YXAsICJzd2FwIiApOwp9