結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー human
提出日時 2023-04-25 14:41:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 5,487 bytes
コンパイル時間 4,275 ms
コンパイル使用メモリ 270,172 KB
実行使用メモリ 4,372 KB
スコア 6,713,843
最終ジャッジ日時 2023-04-25 14:42:26
合計ジャッジ時間 34,097 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
  int elapsed() {
    end_time = chrono::system_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(end_time - start_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 = 900;
const int N = 100;
const int M = 8;
const int alpha = 5;
const int alpha2 = 25;
const int INF = 101010101;

PII planets[N];
PII stations[M];

int p2p[N][N];

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

  void set() {
    rep(i, N) rep(j, N) {dist[i][j] = alpha2 * ((planets[i].X-planets[j].X)*(planets[i].X-planets[j].X) + (planets[i].Y-planets[j].Y)*(planets[i].Y-planets[j].Y)); next[i][j] = j;}

  }
  void calc() {
    rep(k, N) rep(i, N) rep(j, N) {
      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 >> planets[i].X >> planets[i].Y;
}

void print_ans(VI &junban)
{
  rep(i, M) cout << stations[i].X << " " << stations[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) cout << "1 " << i+1 << endl;
}

void solve()
{
  double start_temp = 500;
  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]];

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

    int a, b; select_2(a, b, 100); // (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() / TIME_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_ans(junban);
}

int main()
{
  load_data();
  rep(i, M) {stations[i].X = 0; stations[i].Y = 0;}
  warshall.set();
  warshall.calc();

  solve();
}
0