結果

問題 No.5001 排他的論理和でランニング
ユーザー どらら
提出日時 2018-03-16 23:03:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,440 bytes
コンパイル時間 1,401 ms
実行使用メモリ 9,884 KB
スコア 0
最終ジャッジ日時 2020-03-12 19:29:53
ジャッジサーバーID
（参考情報） 		judge9 /
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <sys/time.h>
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<double>(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<int> v;
  
  vector<int> 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<int> solve(const vector<int>& 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<int> v;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }

  Solver solver;
  vector<int> result = solver.solve(v, M);

  rep(i,result.size()){
    if(i>0) cout << " ";
    cout << result[i];
  }
  cout << endl;
  
  return 0;
}
0