結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 hiikunZ
|
| 提出日時 | 2022-07-30 17:11:36 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 964 ms / 1,000 ms |
| コード長 | 7,507 bytes |
| コンパイル時間 | 2,964 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 7,281,292 |
| 最終ジャッジ日時 | 2022-07-30 17:12:11 |
| 合計ジャッジ時間 | 34,227 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using std::chrono::system_clock;
using std::chrono::seconds;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 0;//2024948111;
ld dotorad(ld K){return PI * K / 180.0;}
ld radtodo(ld K){return K * 180.0 / PI;}
mt19937 mt;
void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}
const ll N = 100,M = 8;
ll A[N],B[N],C[M],D[M];
ll CC[M],DD[M];
ll flag = 0;
ll X[N],P[N],XX[N],PP[N],IDID[N];
ll UPD;
ll Dis[N][N],DA[N][N],DB[N][N];
ll gomi;
ll now_score;
ll old_score;
ld used_time;
const ld starttemp = 100;
const ld endtemp = 1;
ld temp;
const ld time_limit = 0.96;
const ll BIG = (1LL << 30);
system_clock::time_point start;
vector<ll> ans1,ans2;
void calc_ans(){
now_score = 0;
for(ll i = 0;i < N;i++){
ll dis = MAX,a = -1;
for(ll j = 0;j < M;j++){
ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
if(d < dis){
dis = d;
a = j;
}
}
now_score += dis;
X[i] = a;
P[i] = dis;
}
}
int main(){
start = system_clock::now();
cin >> gomi >> gomi;
for(ll i = 0;i < N;i++) cin >> A[i] >> B[i];
for(ll i = 0;i < N;i++) X[i] = i;
X[N] = 0;
C[0] = 160;D[0] = 160;
C[1] = 160;D[1] = 500;
C[2] = 160;D[2] = 890;
C[3] = 500;D[3] = 330;
C[4] = 500;D[4] = 670;
C[5] = 890;D[5] = 160;
C[6] = 890;D[6] = 500;
C[7] = 890;D[7] = 890;
calc_ans();
used_time = 0;
temp = starttemp + (endtemp - starttemp) * used_time / time_limit;
for(ll i = 0;i < N;i++){
XX[i] = X[i];
PP[i] = P[i];
}
while(1){
for(ll w = 0;w < 1000;w++){
ll ty = mt() % 2;
if(ty < 1){
ll id = mt() % M;
ll x = mt() % 1001;
ll y = mt() % 1001;
ll new_score = 0;
swap(C[id],x);
swap(D[id],y);
UPD = 0;
for(ll i = 0;i < N;i++){
if(X[i] == id){
ll dis = MAX,a = -1;
for(ll j = 0;j < M;j++){
ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
if(d < dis){
dis = d;
a = j;
}
}
new_score += dis;
PP[UPD] = dis;
XX[UPD] = a;
IDID[UPD] = i;
UPD++;
}
else{
const ll j = id;
ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
if(P[i] > d){
PP[UPD] = d;
XX[UPD] = id;
IDID[UPD] = i;
UPD++;
new_score += d;
}
else new_score += P[i];
}
}
double probability = exp((now_score - new_score) / temp);
bool FORCE_NEXT = probability > (ld)(mt() % BIG) / BIG;
if(FORCE_NEXT){
now_score = new_score;
for(ll i = 0;i < UPD;i++){
X[IDID[i]] = XX[i];
P[IDID[i]] = PP[i];
}
}
else{
swap(C[id],x);
swap(D[id],y);
}
}
else if(ty < 2){
ll id = mt() % M;
ll x = C[id] + 80 - mt() % 40;
ll y = D[id] + 80 - mt() % 40;
if(x < 0 || x > 1000 || y < 0 || y > 1000) continue;
ll new_score = 0;
swap(C[id],x);
swap(D[id],y);
UPD = 0;
for(ll i = 0;i < N;i++){
if(X[i] == id){
ll dis = MAX,a = -1;
for(ll j = 0;j < M;j++){
ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
if(d < dis){
dis = d;
a = j;
}
}
new_score += dis;
PP[UPD] = dis;
XX[UPD] = a;
IDID[UPD] = i;
UPD++;
}
else{
const ll j = id;
ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
if(P[i] > d){
PP[UPD] = d;
XX[UPD] = id;
IDID[UPD] = i;
UPD++;
new_score += d;
}
else new_score += P[i];
}
}
double probability = exp((now_score - new_score) / temp);
bool FORCE_NEXT = probability > (ld)(mt() % BIG) / BIG;
if(FORCE_NEXT){
now_score = new_score;
for(ll i = 0;i < UPD;i++){
X[IDID[i]] = XX[i];
P[IDID[i]] = PP[i];
}
}
else{
swap(C[id],x);
swap(D[id],y);
}
}
}
used_time = duration_cast<microseconds>(system_clock::now() - start).count() * 1e-6;
if(used_time > time_limit) break;
temp = starttemp + (endtemp - starttemp) * used_time / time_limit;
}
calc_ans();
for(ll i = 0;i < M;i++) cout << C[i] << " " << D[i] << endl;
vector<ll> B,PER(M);
ll tp = 998244353;
for(ll i = 0;i < M;i++){
PER[i] = i;
}
do{
ll s = 0;
for(ll i = 0;i < M;i++){
ll I = PER[i];
ll J = PER[(i + 1) % M];
s += (C[I] - C[J]) * (C[I] - C[J]) + (D[I] - D[J]) * (D[I] - D[J]);
}
if(tp > s){
tp = s;
B = PER;
}
}
while(next_permutation(PER.begin(),PER.end()));
for(ll I = 0;I < M;I++){
ll i = B[I];
ans1.emplace_back(2);
ans2.emplace_back(i + 1);
for(ll j = 0;j < N;j++){
if(X[j] == i){
ans1.emplace_back(1);
ans2.emplace_back(j + 1);
ans1.emplace_back(2);
ans2.emplace_back(i + 1);
}
}
}
ll V = (ll)ans1.size(),I = -1;
for(ll i = 0;i < V;i++){
ans1.emplace_back(ans1[i]);
ans2.emplace_back(ans2[i]);
if(ans1[i] == 1 && ans2[i] == 1) I = i;
}
cout << V + 1 << endl;
for(ll i = I;i < I + V;i++) cout << ans1[i] << " " << ans2[i] << endl;
cout << "1 1" << endl;
}