#include #include using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; unsigned int xor128(){ static unsigned int x=123456789, y=362436069, z=521288629, w=88675123; unsigned int t; t=(x^(x<<11)); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } inline double frand(){ return xor128()%UINT_MAX/static_cast(UINT_MAX); } static const double PI = 3.14159265358979323846264338; double normal_rand(double mu, double sigma2){ double sigma = sqrt(sigma2); double u1 = frand(), u2 = frand(); double z1 = sqrt(-2*log(u1)) * cos(2*PI*u2); //double z2 = sqrt(-2*log(u1)) * sin(2*PI*u2); return mu + sigma*z1; } class Timer { double start_time; double getNow(){ struct timeval t; gettimeofday(&t, NULL); return t.tv_sec + t.tv_usec * 1e-6; /* unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2800000000.0; */ } public: void start(){ start_time = getNow(); } double getSec(){ return getNow()-start_time; } }; class Solver { const double time_limit = 4.95; Timer timer; int N, M; vector v; vector result, best_result; int score, best_score; int prev_rv, prev_rs; int prev_score; int moveNeighbor(double sec){ prev_score = score; int rv = xor128()%(v.size()); int rs = xor128()%M; if(v[rv] != -1){ swap(v[rv], result[rs]); prev_rv = rv; prev_rs = rs; score = 0; rep(i,result.size()){ score ^= result[i]; } score *= -1; } return score - prev_score; } void moveUndo(){ swap(v[prev_rv], result[prev_rs]); score = prev_score; } double calcTemp(double sec){ double start_temp = 10000.0; double end_temp = 0.1; double now_temp = start_temp + (end_temp - start_temp) * sec / time_limit; return now_temp; } void updateBestScore(){ best_result = result; best_score = score; } public: vector solve(const vector& in, int M_){ timer.start(); v = in; N = v.size(); M = M_; rep(i,M){ result.push_back(v[N-1-i]); } rep(i,M){ v.pop_back(); } score = 0; rep(i,result.size()){ score ^= result[i]; } score *= -1; updateBestScore(); double sec = timer.getSec(); double T = calcTemp(sec); while(true){ sec = timer.getSec(); if(sec > time_limit) break; bool undo = false; int delta = moveNeighbor(sec); if(delta < 0){ if(exp(delta / T) >= frand()){ ; }else{ undo = true; } } if(undo) moveUndo(); if(best_score > score){ updateBestScore(); cerr << "BestScore: " << best_score << endl; } T = calcTemp(sec); } cerr << "BestScore: " << best_score << endl; return best_result; } }; int main(){ int N, M; cin >> N >> M; vector v; rep(i,N){ int a; cin >> a; v.push_back(a); } Solver solver; vector result = solver.solve(v, M); rep(i,result.size()){ if(i>0) cout << " "; cout << result[i]; } cout << endl; return 0; }