結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_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