結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー ronnya
提出日時 2022-07-30 17:04:14
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 1,000 ms
コード長 4,165 bytes
コンパイル時間 1,985 ms
実行使用メモリ 6,952 KB
スコア 4,611,615
最終ジャッジ日時 2022-07-30 17:04:33
合計ジャッジ時間 4,827 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

using ll   = long long;     using ld   = long double;
using pll  = pair<ll, ll>;  using pld  = pair<ld, ld>;
using vll  = vector<ll>;    using vld  = vector<ld>;
using vpll = vector<pll>;   using vpld = vector<pld>;
using vvll = vector<vll>;   using vvld = vector<vld>;
template<class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

#define rep(i, a, b) for(ll i = (ll)a; i < (ll)b; i++)
#define irep(i, v) for(auto i = (v).begin(); i != (v).end(); i++)
#define SZ(v) (ll)(v).size()
#define ALL(v) (v).begin(), (v).end()
#define SHIFT(a) (1LL << (ll)a)
#define endl '\n'

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-10;
const ld PI  = M_PI;

ll power(ll x, ll y){ ll res = 1; while(y > 0){ if(y & 1){ res *= x; } x *= x; y >>= 1; } return res; }
bool in_grid(ll x, ll y, ll h, ll w){ return (0 <= x && x < h && 0 <= y && y < w); }
template<class T> void pvec(vector<T> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ if(i){ cout << " "; } cout << vec[i]; } cout << endl; }
template<class T> void pvvec(vector<vector<T>> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ for(ll j = 0; j < (ll)vec[i].size(); j++){ if(j){ cout << " "; } cout << vec[i][j]; } cout << endl; } }
template<class T> void asort(vector<T> &vec){ sort(ALL(vec)); }
template<class T> void rsort(vector<T> &vec){ sort(ALL(vec)); reverse(ALL(vec)); }

class timer{
  private:
    chrono::system_clock::time_point st, ed;
  public:
    timer() {start();}
    void start(){
      st = chrono::system_clock::now(); // 開始
    }
    void stop(){
      ed = chrono::system_clock::now(); // 終了
    }
    void print(string s = ""){
      if(s != "") cout << s << " ";
      auto elapsed = chrono::duration_cast<chrono::milliseconds>(ed - st).count();
      cout << elapsed << "ms" << endl;
    }
    void stop2(string s = ""){
      stop(); print(s);
    }
};

ll n, m;
vpll vec(100);
vpll sta(8);

vpll route;

ll dis(pll &p1, pll &p2){
  ll x = p1.first - p2.first;
  ll y = p1.second - p2.second;
  return (x * x + y * y);
}

ll total(vpll &r){
  ll res = 0;
  rep(i, 0, SZ(r) - 1){
    ll d;
    pll p1 = (r[i].first == 1 ? vec[r[i].second] : sta[r[i].second]);
    pll p2 = (r[i + 1].first == 1 ? vec[r[i + 1].second] : sta[r[i + 1].second]);
    if(r[i].first == 1 && r[i + 1].first == 1){
      d = 25 * dis(p1, p2);
    }
    else if(r[i].first == 2 && r[i + 1].first == 2){
      d = dis(p1, p2);
    }
    else{
      d = 5 * dis(p1, p2);
    }
    res += d;
  }
  return res;
}

//cout << ll(1000000000 / (1000 + sqrt(total(tmp)))) << endl;



//using mint = modint<MOD>;

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  cout << fixed << setprecision(20);


  timer T;

  cin >> n >> m;
  rep(i, 0, n) cin >> vec[i].first >> vec[i].second;

  vector<pair<ld, ll>> rad;
  rep(i, 1, n){
    ll x = vec[i].first - vec[0].first;
    ll y = vec[i].second - vec[0].second;
    ld theta = atan2(y, x);
    rad.push_back({theta, i});
  }
  sort(ALL(rad));

  vpll tmp = {{1, 0}};
  rep(i, 0, SZ(rad)) tmp.push_back({1, rad[i].second});
  tmp.push_back({1, 0});

  ll score = INF;
  vpll anssta, ansres;

  for(ll itr = 0; itr < 2000; itr++){
    rep(i, 0, m){
      sta[i] = {rand() % 1000, rand() % 1000};
    }

    vpll res;

    rep(i, 0, SZ(tmp) - 1){
      res.push_back(tmp[i]);
      pll p1 = vec[tmp[i].second], p2 = vec[tmp[i + 1].second];
      ll d1 = 25 * dis(p1, p2);
      min_queue<pll> que;
      rep(j, 0, SZ(sta)){
        pll p3 = sta[j];
        ll d2 = 5 * dis(p1, p3) + 5 * dis(p3, p2);
        que.push({d2, j});
      }
      pll p = que.top();
      if(p.first < d1) res.push_back({2, p.second});
    }
    res.push_back({1, 0});

    ll t = total(res);
    if(t < score){
      t = score;
      anssta = sta;
      ansres = res;
    }
  }

  rep(i, 0, m) cout << anssta[i].first << " " << anssta[i].second << endl;
  cout << SZ(ansres) << endl;
  rep(i, 0, SZ(ansres)) cout << ansres[i].first << " " << ansres[i].second + 1 << endl;

  //T.stop2();


  return 0;
}
0