#862876 (C++23) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	hangry
提出日時	2023-04-25 18:35:34
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,505 bytes
コンパイル時間	5,740 ms
コンパイル使用メモリ	274,044 KB
実行使用メモリ	4,496 KB
スコア	6,483,409
最終ジャッジ日時	2023-04-25 18:36:17
合計ジャッジ時間	40,708 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	954 ms 4,368 KB
testcase_01	AC	953 ms 4,368 KB
testcase_02	AC	954 ms 4,372 KB
testcase_03	AC	954 ms 4,372 KB
testcase_04	AC	953 ms 4,368 KB
testcase_05	AC	953 ms 4,372 KB
testcase_06	AC	954 ms 4,496 KB
testcase_07	AC	954 ms 4,372 KB
testcase_08	AC	953 ms 4,368 KB
testcase_09	AC	954 ms 4,368 KB
testcase_10	AC	954 ms 4,372 KB
testcase_11	AC	954 ms 4,372 KB
testcase_12	AC	954 ms 4,372 KB
testcase_13	AC	956 ms 4,372 KB
testcase_14	AC	953 ms 4,372 KB
testcase_15	AC	953 ms 4,376 KB
testcase_16	AC	956 ms 4,368 KB
testcase_17	AC	953 ms 4,368 KB
testcase_18	AC	953 ms 4,372 KB
testcase_19	AC	953 ms 4,368 KB
testcase_20	AC	954 ms 4,372 KB
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	AC	954 ms 4,368 KB
testcase_24	AC	954 ms 4,368 KB
testcase_25	AC	954 ms 4,372 KB
testcase_26	AC	954 ms 4,368 KB
testcase_27	AC	953 ms 4,376 KB
testcase_28	AC	953 ms 4,368 KB
testcase_29	AC	954 ms 4,368 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
//#include <atcoder>
using namespace std;
//using namespace atcoder;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repab(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define repabc(i, a, b, c) for (int i = (int)(a); i <= (int)(b); i += c)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrepab(i, a, b) for (int i = (int)(b); i >= (int)(a); i--)
#define rrepabc(i, a, b, c) for (int i = (int)(b); i >= (int)(a); i-=c)
#define printl(...) cerr << "LINE=" << __LINE__ << " "; print(__VA_ARGS__)
#define print_data(variable) cerr << "[DATA] " << #variable << " = " << variable << endl;
#define X first
#define Y second

#define ARGS_SIZE_(a1,a2,a3,a4,a5,a6,a7,a8,a9,size,...) size
#define ARGS_SIZE(...) ARGS_SIZE_(__VA_ARGS__,9,8,7,6,5,4,3,2,1)
#define DB_1(x) #x << "=" << (x) <<
#define DB_2(x, ...) #x << "=" << (x) << ", " << DB_1(__VA_ARGS__)
#define DB_3(x, ...) #x << "=" << (x) << ", " << DB_2(__VA_ARGS__)
#define DB_4(x, ...) #x << "=" << (x) << ", " << DB_3(__VA_ARGS__)
#define DB_5(x, ...) #x << "=" << (x) << ", " << DB_4(__VA_ARGS__)
#define DB_6(x, ...) #x << "=" << (x) << ", " << DB_5(__VA_ARGS__)
#define DB_7(x, ...) #x << "=" << (x) << ", " << DB_6(__VA_ARGS__)
#define DB_8(x, ...) #x << "=" << (x) << ", " << DB_7(__VA_ARGS__)
#define DB_9(x, ...) #x << "=" << (x) << ", " << DB_8(__VA_ARGS__)
#define DB__(size, ...) DB_##size(__VA_ARGS__)
#define DB_(size, ...) DB__(size, __VA_ARGS__)
#define DB(...) do {cerr << DB_(ARGS_SIZE(__VA_ARGS__), __VA_ARGS__) endl;} while (0)

void print() {}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail)
{
  cerr << head;
  if (sizeof...(Tail) == 0) cerr << endl;
  else cerr << ", ";
  print(forward<Tail>(tail)...);
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
  os << "{";
  for (int i = 0; i<vec.size(); i++) {
    os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  }
  os << "}";
  return os;
}

unsigned int randxor()
{
    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)) );
}
struct Timer {
  chrono::system_clock::time_point start_time = chrono::system_clock::now();
  chrono::system_clock::time_point end_time = chrono::system_clock::now();
  chrono::system_clock::time_point lap_time = chrono::system_clock::now();
  int elapsed() {
    end_time = chrono::system_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
  }
  void lap() {
    lap_time = chrono::system_clock::now();
  }
  int elapsed_lap() {
    end_time = chrono::system_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(end_time - lap_time).count();
  }
  
} timer;

void select_2(int &one, int &other, int n) { // [0, n)から相異なる２つを選択
  one = randxor() % n;
  other = randxor() % (n-1);
  if ( one <= other ) other++;
}

//static const int dx[] = {0,-1,0,1,1,-1,-1,1};
//static const int dy[] = {-1,0,1,0,1,1,-1,-1};
//static const char dir[] = {'L','U','R','D'};

const int TIME_LIMIT = 950;
const int N = 100;
const int M = 8;
const int NM = N + M;
const int alpha = 5;
const int alpha2 = 25;
const int INF = 101010101;

PII pos[NM]; // [0, N)が惑星，[N, N+M)がステーション

struct FloydWarshall
{
  int dist[NM][NM];
  int next[NM][NM];

  void set() {
    rep(i, NM) rep(j, NM) {
      dist[i][j] = (pos[i].X-pos[j].X)*(pos[i].X-pos[j].X) + (pos[i].Y-pos[j].Y)*(pos[i].Y-pos[j].Y); 
      if ( i < N && j < N ) dist[i][j] *= alpha2;
      else if ( i < N || j < N ) dist[i][j] *= alpha;
      next[i][j] = j;
    }
  }
  void calc() {
    rep(k, NM) rep(i, NM) rep(j, NM) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
        next[i][j] = next[i][k];
      }
    }
  }
  VI get_path(int s, int t) {
    VI ret;
    for (int cur = s; cur != t; cur = next[cur][t]) {
      ret.push_back(cur);
    }
    ret.push_back(t);
    return ret;
  }
} warshall;


void load_data()
{
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int _;
  cin >> _ >> _;
  rep(i, N) cin >> pos[i].X >> pos[i].Y;
}

void print_ans(VI &junban)
{
  repab(i, N, NM-1) cout << pos[i].X << " " << pos[i].Y << endl;
  VI ans;
  rep(i, N) {
    VI add = warshall.get_path(junban[i], junban[i+1]);
    for (int j: add) ans.push_back(j);
  }
  cout << ans.size() << endl;
  for (int i: ans) {
    if ( i < N ) cout << "1 " << i+1 << endl;
    else cout << "2 " << i+1-N << endl;
  }
}

void solve(int &best_cost, VI &best_junban)
{
  double start_temp = 100000;
  const double end_temp = 0;
  VI junban; rep(i, N) junban.push_back(i); junban.push_back(0);
  int now_cost = 0; rep(i, N) now_cost += warshall.dist[junban[i]][junban[i+1]];

  timer.lap();
  int each_limit = 950;

  int iter = 0;
  while ( true ) {
    if ( iter % 100 == 0 ) {
      if ( timer.elapsed_lap() >= each_limit || timer.elapsed() > TIME_LIMIT ) break;
    }
    iter++;

    int a, b; select_2(a, b, N); // (a, a+1)(b, b+1)間をswap
    if ( a > b ) swap(a, b);
    int diff = warshall.dist[junban[a]][junban[b]] + warshall.dist[junban[a+1]][junban[b+1]] - warshall.dist[junban[a]][junban[a+1]] - warshall.dist[junban[b]][junban[b+1]];  
    double temp = start_temp + (end_temp - start_temp) * timer.elapsed_lap() / each_limit;
    double prob = exp(-(double)diff/temp);
    if ( prob > (randxor() % 10000)/10000.0 ) {
      reverse(junban.begin() + a + 1, junban.begin() + b + 1);
      now_cost += diff;
    }
  }
  double score = 1000000000 / (1000.0 + sqrt((double)now_cost));
  print_data(score);
  print_data(iter);
  //print_ans(junban);
  if ( best_cost > now_cost ) {
    best_cost = now_cost;
    best_junban = junban;
  }
}

int main()
{
  load_data();
  int best_cost = INF;
  VI best_junban;
  while ( timer.elapsed() < TIME_LIMIT ) {
    //rep(i, M) {pos[i+N].X = 100*(i+1); pos[i+N].Y = 100*(i+1);}//////
    rep(i, M) {pos[i+N].X = 100 + randxor() % 800; pos[i+N].Y = 100 + randxor() % 800;}//////
    warshall.set();
    warshall.calc();
    solve(best_cost, best_junban);
  }
  double score = 1000000000  / (1000.0 + sqrt((double)best_cost));
  print_ans(best_junban);
}

yukicoder

結果

テストケース

ソースコード