Submission #1872782

---

Source Code Expand

#include <bits/stdc++.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));
}
 
class Timer {
  double start_time;
  double GetNow(){
    unsigned long long a, d;
    __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
#ifdef LOCAL
    return (d << 32 | a) / 3400000000.0;
#else
    return (d << 32 | a) / 2800000000.0;
#endif
  }
public:
  void Start(){
    start_time = GetNow();
  }
  double GetSec(){
    return GetNow()-start_time;
  }
};
 
template<int MAX_V, int MAX_N>
class SA {
  const double kTimeLimit = 29.9;
  const int kVx[8] = {-1,0,1,1,1,0,-1,-1};
  const int kVy[8] = {1,1,1,0,-1,-1,-1,0};
  
  Timer timer;
  
  int g_v, g_e;
  int gemb_v, gemb_e, gemb_n;
  int g[MAX_V][MAX_V];
  
  int gemb_score;
  int gemb[MAX_N][MAX_N];
  int best_gemb_score;
  int best_gemb[MAX_N][MAX_N];
 
  int sg[MAX_V][MAX_V];
  int sgemb[MAX_N][MAX_N];
 
  int save_y, save_x;
  int save_before, save_after;
  
  //mt19937 mt;
  //uniform_real_distribution<double> urd;
 
  inline bool InRange(int y, int x){
    return 0 <= y && y < gemb_n && 0 <= x && x < gemb_n;
  }
 
  double Frand() {
    return xor128()%UINT_MAX/static_cast<double>(UINT_MAX);
    //return urd(mt);
  }
  
  void UpdateBestGemb(){
    best_gemb_score = gemb_score;
    rep(i,gemb_n){
      rep(j,gemb_n){
        best_gemb[i][j] = gemb[i][j];
      }
    }
  }
 
  // Gembの初期状態を作成する
  void InitGemb(){
 
    vector<bool> can_move(g_v, true);
    vector<int> pos(g_v, -1);
 
    // ランダムに配置
    /*
    rep(i,g_v){
      while(true){
        int r = mt() % gemb_v;
        int y = r / gemb_n;
        int x = r % gemb_n;
        
        if(gemb[y][x] == -1){
          gemb[y][x] = i;
          pos[i] = r;
          break;
        }
      }
    }
      */
 
    int cnt_max = 0;
    rep(i,g_v){
      int cnt = 0;
      rep(j,g_v){
        if(g[i][j] >= 0) cnt++;
      }
      cnt_max = max(cnt_max, cnt);
    }
 
    // できるだけ隣接頂点を近くに配置
    int window_size = 5;
    while(true){
      int num_cell = (window_size*2)*(window_size*2);
      if(num_cell * 0.5 > cnt_max) break;
      window_size++;
    }
    rep(i,g_v){
      int r, y, x;
      if(pos[i] == -1){
        while(true){
          r = xor128() % gemb_v;
          y = r / gemb_n;
          x = r % gemb_n;
          
          if(gemb[y][x] == -1){
            gemb[y][x] = i;
            pos[i] = r;
            break;
          }
        }
      }else{
        r = pos[i];
        y = r / gemb_n;
        x = r % gemb_n;
      }
      // iに隣接する頂点をiの近くに配置
      rep(j,g_v) if(g[i][j] >= 0 && pos[j] == -1){
        int iter = 1000;
        while(--iter){
          int cand_y = y + xor128() % (window_size * 2) - window_size;
          int cand_x = x + xor128() % (window_size * 2) - window_size; 
          if(!InRange(cand_y,cand_x)) continue;
          if(gemb[cand_y][cand_x] != -1) continue;
          gemb[cand_y][cand_x] = j;
          pos[j] = cand_y * gemb_n + cand_x;
          break;
        }
      }
    }
 
 
    // 頂点を適当に伸ばせるだけ伸ばす
    bool flg = true;
    int num_non = g_v;
    while(flg){
      flg = false;
      rep(i,g_v) if(can_move[i]){
        int p = pos[i];
        int y = p / gemb_n;
        int x = p % gemb_n;
 
        vector<int> ok;
        rep(k,8){
          int ny = y + kVy[k];
          int nx = x + kVx[k];
          if(!InRange(ny, nx)) continue;
          if(gemb[ny][nx] != -1) continue;
          ok.push_back(k);
        }
 
        if(ok.size() == 0){
          can_move[i] = false;
        }else{
          int rk = xor128() % (ok.size());
          int ny = y + kVy[ok[rk]];
          int nx = x + kVx[ok[rk]];
          gemb[ny][nx] = i;
          pos[i] = ny * gemb_n + nx;
          num_non++;
          flg = true;
        }
      }
    }
 
#ifdef LOCAL
    rep(i,gemb_n){
      rep(j,gemb_n){
        fprintf(stderr, "%4d", gemb[i][j]);
      }
      fprintf(stderr, "\n");
    }
#endif
 
   /*
    int cnt = 0;
    rep(i,gemb_n){
      rep(j,gemb_n){
        best_gemb[i][j] = gemb[i][j] = cnt++;
        if(cnt >= g_v) break;
      }
      if(cnt >= g_v) break;
    }
    */
    UpdateBestGemb();
    gemb_score = CalcScore();
    cerr << "FirstScore: " << gemb_score << endl;
  }
  
  // Gembの現状態の近傍の状態へ更新する
  int MoveNeighbor(){
    save_y = save_x = -1;
    
    int r = xor128() % gemb_v;
    int y = r / gemb_n;
    int x = r % gemb_n;
 
    int k = xor128() % 8;
 
    int ny = y + kVy[k];
    int nx = x + kVx[k];
 
    if(!InRange(ny, nx)) return 0;
    if(gemb[y][x] == -1 && gemb[ny][nx] == -1) return 0;
 
    int before_score = gemb_score;
    save_y = ny;
    save_x = nx;
    save_before = gemb[ny][nx];
    save_after = gemb[y][x];
    gemb[ny][nx] = gemb[y][x];
    int after_score = CalcScore();
    gemb_score = after_score;
    
    return after_score - before_score;
  }
 
  // ひとつ前の状態に戻す
  void MoveUndo(int delta){
    gemb_score -= delta;
    if(save_y < 0) return;
    gemb[save_y][save_x] = save_before;
  }
 
  // 温度の更新
  double CalcTemp(double sec, double T){
    //return T * 0.999;
    return 200.0 * pow(0.7, sec);
  }
 
  // 反復回数の更新
  int CalcLen(double sec, int R){
    //return R;
    //return -29 * sec + 300;
    //if(sec < kTimeLimit/2) return 200;
    if(sec < kTimeLimit*4/5.0) return 200;
    else return 10;
  }
 
  // スコア計算
  int CalcScore(){
    rep(i,MAX_N) rep(j,MAX_N) sgemb[i][j] = -1;
    rep(i,MAX_V) rep(j,MAX_V) sg[i][j] = -1;
    
    vector<int> cnt(MAX_V,0);
    rep(i,gemb_n){
      rep(j,gemb_n){
        if(gemb[i][j] == -1) continue;
        if(sgemb[i][j] != -1) continue;
 
        if(cnt[gemb[i][j]] != 0) return 0;
 
        queue<pair<int,int>> que;
        que.push(make_pair(i,j));
        while(!que.empty()){
          pair<int,int> p = que.front(); que.pop();
          if(sgemb[p.first][p.second] != -1) continue;
          if(gemb[p.first][p.second] != gemb[i][j]) continue;
          sgemb[p.first][p.second] = gemb[i][j];
          cnt[gemb[i][j]]++;
 
          rep(k,8){
            int ny = p.first + kVy[k];
            int nx = p.second + kVx[k];
            if(!InRange(ny,nx)) continue;
            if(sgemb[ny][nx] != -1) continue;
            if(gemb[p.first][p.second] != gemb[ny][nx]){
              if(g[gemb[p.first][p.second]][gemb[ny][nx]] >= 0){
                sg[gemb[p.first][p.second]][gemb[ny][nx]] = g[gemb[p.first][p.second]][gemb[ny][nx]];
                sg[gemb[ny][nx]][gemb[p.first][p.second]] = g[gemb[p.first][p.second]][gemb[ny][nx]];
              }
            }else{
              que.push(make_pair(ny,nx));
            }
          }
        }
      }
    }
    int add_score = 0;
    int loss_score = 0;
    int bonus_score = 100000;
    rep(i,g_v){
      if(cnt[i] == 0) return 0;
      loss_score -= cnt[i]-1;
      rep(j,g_v){
        if(g[i][j] >= 0 && sg[i][j] != g[i][j]){
          bonus_score = 0;
        }
        if(sg[i][j] == -1) continue;
        add_score += sg[i][j];
      }
    }
    add_score /= 2;
    
    return 5000 + add_score + loss_score + bonus_score;
  }
  
public:
  //SA():mt(random_device()()){
  SA(){
    timer.Start();
    Init();
  }
 
  void Init(){
    rep(i,MAX_V) rep(j,MAX_V) g[i][j] = -1;
    rep(i,MAX_N) rep(j,MAX_N) best_gemb[i][j] = gemb[i][j] = -1;
    gemb_score = 0;
    best_gemb_score = -1;
  }
  
  void SetGve(int V, int E){
    g_v = V;
    g_e = E;
  }
  
  void SetEmbve(int V, int E){
    gemb_v = V;
    gemb_e = E;
    gemb_n = (int)sqrt(V);
    assert(gemb_n * gemb_n == gemb_v);
  }
  
  void SetG(int u, int v){
    g[u][v] = 100;
    g[v][u] = 100;
  }
    
  void Solve(){
    // 初期解
    InitGemb();
 
    double sec = timer.GetSec();
    
    // 初期パラメータ
    double T = CalcTemp(sec, 150);
    int R = CalcLen(sec, 10);
 
    int cnt = 0;
    while(true){
      sec = timer.GetSec();
      if(sec > kTimeLimit) break;
      //if(T < 0.005) break;
 
      rep(i,R){
        // 近傍移動
        int delta = MoveNeighbor();
        // 受理するかどうか
        if(gemb_score == 0){ // 受理しない
          MoveUndo(delta);           
        }else if(delta >= 0){ // 受理する
          ;
        }else{
          if(exp(delta / T) >= Frand()){ // 受理する
            ;
          }else{ // 受理しない
            MoveUndo(delta); 
          }
        }
 
        // ベスト解を記録
        if(best_gemb_score < gemb_score){
          UpdateBestGemb();
        }
 
        cnt++;
      }
 
 
      /*
      cerr << sec << "\t" << best_gemb_score << "\t" << gemb_score << "\t" << T << endl;
      if(cnt % 10000 == 0){
        rep(i,gemb_n){
          rep(j,gemb_n){
            fprintf(stderr, "%4d", best_gemb[i][j]);
          }
          fprintf(stderr, "\n");
        }
      }
       */
      
      T = CalcTemp(sec, T);
      R = CalcLen(sec, R);
    }
  }
  
  void PrintResult(){
    map<int,vector<int>> ret;
    rep(i,gemb_n){
      rep(j,gemb_n){
        if(best_gemb[i][j] != -1){
          int g_p = best_gemb[i][j];
          int gemb_p = i * gemb_n + j;
          ret[g_p+1].push_back(gemb_p+1);
        }
      }
    }
    FOR(it,ret){
      cout << (it->second).size();
      rep(i,(it->second).size()){
        cout << " " << (it->second)[i];
      }
      cout << endl;
    }
 
    cerr << "BestScore: " << best_gemb_score << endl;
#ifdef LOCAL
    rep(i,gemb_n){
      rep(j,gemb_n){
        fprintf(stderr, "%4d", best_gemb[i][j]);
      }
      fprintf(stderr, "\n");
    }
#endif
  }
};
 
 
int main(){
  SA<500,65> sa;
 
  int G_V, G_E;
  cin >> G_V >> G_E;
  sa.SetGve(G_V, G_E);
 
  rep(i,G_E){
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    sa.SetG(u, v);
  }
 
  int Gemb_V, Gemb_E;
  cin >> Gemb_V >> Gemb_E;
  sa.SetEmbve(Gemb_V, Gemb_E);
  
  rep(i,Gemb_E){
    int a, b;
    cin >> a >> b;
  }
 
  sa.Solve();
 
  sa.PrintResult();
 
  return 0;
}

Submission Info

Judge Result