結果

問題 No.5007 Steiner Space Travel
ユーザー MichirakaraMichirakara
提出日時 2023-04-23 21:19:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 6,893 bytes
コンパイル時間 2,376 ms
コンパイル使用メモリ 200,152 KB
実行使用メモリ 4,372 KB
スコア 4,521,707
最終ジャッジ日時 2023-04-23 21:19:59
合計ジャッジ時間 4,129 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 1 ms
4,372 KB
testcase_03 AC 2 ms
4,368 KB
testcase_04 AC 2 ms
4,372 KB
testcase_05 AC 2 ms
4,372 KB
testcase_06 AC 2 ms
4,372 KB
testcase_07 AC 2 ms
4,372 KB
testcase_08 AC 2 ms
4,368 KB
testcase_09 AC 1 ms
4,368 KB
testcase_10 AC 2 ms
4,372 KB
testcase_11 AC 1 ms
4,372 KB
testcase_12 AC 2 ms
4,368 KB
testcase_13 AC 1 ms
4,368 KB
testcase_14 AC 2 ms
4,372 KB
testcase_15 AC 2 ms
4,372 KB
testcase_16 AC 2 ms
4,372 KB
testcase_17 AC 2 ms
4,372 KB
testcase_18 AC 2 ms
4,368 KB
testcase_19 AC 1 ms
4,372 KB
testcase_20 AC 2 ms
4,368 KB
testcase_21 AC 1 ms
4,372 KB
testcase_22 AC 2 ms
4,372 KB
testcase_23 AC 2 ms
4,372 KB
testcase_24 AC 1 ms
4,372 KB
testcase_25 AC 2 ms
4,372 KB
testcase_26 AC 2 ms
4,372 KB
testcase_27 AC 2 ms
4,368 KB
testcase_28 AC 2 ms
4,372 KB
testcase_29 AC 2 ms
4,372 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:9: 警告: #pragma once がメインファイルにあります
    8 | #pragma once
      |         ^~~~

ソースコード

diff # 

/**************************************************/
/*
C++ template 
    by michirakara
    「嘘解法は友達」(?)
*/
//include std
#pragma once
#include <cassert>
#include <cfenv>
#include <cfloat>
#include <ciso646>
#include <clocale>
#include <csetjmp>
#include <csignal>
#include <cstdbool>
#include <cinttypes>
#include <charconv>
#include <typeindex>
#include <any>
#include <scoped_allocator>
#include <forward_list>
#include <list>
#include <map>
#include <set>
#include <valarray>
#include <variant>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <condition_variable>
#include <shared_mutex>
#include <codecvt>
#include <future>
#include <regex>
#include <iostream>
#include <random>
#include <ctgmath>
#include <fstream>

using namespace std;

//コンパイラと浮動小数点高速化
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

//cin,endlの高速化
//インタラクティブのときは外す
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
#define endl '\n'

//using
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
using vvi=vector<vi>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;//PLLはY-permが好き

const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=998244353;
const ld PI=3.1415926535897932384626433832795028841971;

const ll dx[]={0,1,0,-1};
const ll dy[]={1,0,-1,0};
const ll dx8[]={0,1,0,-1,1,-1,1,-1};
const ll dy8[]={1,0,-1,0,1,1,-1,-1};

//define
#define itn int//これすき

#define elif else if

/*最終兵器
絶対使うな
#define int long long
*/
 
//マクロ

//min(a,b,....)-> min({a,b,....})
//Pythonのように任意個の要素を入れることの可能なmin()
template<class... T>
constexpr auto min(T... a){
    return min(initializer_list<common_type_t<T...>>{a...});
}
//同じくmax
template<class... T>
constexpr auto max(T... a){
    return max(initializer_list<common_type_t<T...>>{a...});
}

void scan(int& a){cin>>a;}
void scan(unsigned& a){cin>>a;}
void scan(long& a){cin>>a;}
void scan(long long& a){cin>>a;}
void scan(unsigned long long& a){cin>>a;}
void scan(float& a){cin>>a;}
void scan(double& a){cin>>a;}
void scan(long double& a){cin>>a;}
void scan(char& a){cin>>a;}
void scan(string& a){cin>>a;}
template<class T> void scan(vector<T>&);
template<class T,size_t size> void scan(array<T,size>&);
template<class T,class L> void scan(pair<T,L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){for(auto&& i:a)scan(i);};
template<class T> void scan(deque<T>& a){for(auto&& i:a)scan(i);};
template<class T,size_t size> void scan(array<T,size>& a){for(auto&& i:a)scan(i);};
template<class T,class L> void scan(pair<T,L>& a){scan(a.first);scan(a.second);};
template<class T, size_t size> void scan(T(&a)[size]){for(auto&& i:a)scan(i);};
template<class T> void scan(T& a){cin>>a;}
void input(){}
//input(a,b...)-> cin>>a>>b>>...
//input(変数名...)で勝手に入力を受け取ってくれる かしこい
template<class Head,class... Tail>
void input(Head& H,Tail&... T){
    scan(H);input(T...);
}

//INT(a,b)-> int a,b;cin>>a>>b;
//INT(変数名)でintの変数を作ってinputから取ってくれる かしこい
#define INT(...)int __VA_ARGS__; input(__VA_ARGS__)
//LL(a,b)-> long long a,b;cin>>a>>b;
//LL(変数名)でllの変数を作ってinputから取ってくれる かしこい
#define LL(...)ll __VA_ARGS__; input(__VA_ARGS__)

void puts(){cout<<' ';}
void puts(int a){cout<<a;}
void puts(unsigned a){cout<<a;}
void puts(long a){cout<<a;}
void puts(long long a){cout<<a;}
void puts(unsigned long long a){cout<<a;}
void puts(float a){cout<<a;}
void puts(double a){cout<<a;}
void puts(long double a){cout<<a;}
void puts(char a){cout<<a;}
void puts(string a){cout<<a;}
template<class T> void puts(vector<T>);
template<class T,size_t size> void puts(array<T,size>);
template<class T,class L> void puts(pair<T,L>);
template<class T, size_t size> void puts(T[size]);
template<class T> void puts(vector<T> a){if(a.empty())return;puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T> void puts(deque<T> a){if(a.empty())return;puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T,size_t size> void puts(array<T,size> a){puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T,class L> void puts(pair<T,L> a){puts(a.first);cout<<' ';puts(a.second);};
template<class T, size_t size> void puts(T(a)[size]){puts(a[0]);for(auto i=a;++i!=end(a);){cout<<' ';puts(*i);}};
template<class T> void puts(T a){cout<<a;}
void print(){cout<<endl;}
//print(a,b...)ほぼPythonのprintといっしょ <- うれしい
template<class Head,class... Tail>
void print(Head H,Tail... T){
    puts(H);print(T...);
}

//rep1(i,a)-> i in [0,a)
//reps(i,a,b)-> i in [a,b)
//r_p(i,a,b,c)-> i in [a,b) by c
#define rep1(i, a) for(ll i=0; i<(ll)a; i++)
#define reps(i, a, b) for(ll i=a; i<(ll)b; i++)
#define r_p(i, a, b, c) for(ll i=a; i<(ll)b; i+=c)

//rep(i,a)-> i in [0,a)
//rep(i,a,b)-> i in [a,b)
//rep(i,a,b,c)-> i in [a,b) by c
//大体Pythonのfor文と同じrepマクロ
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, r_p, reps, rep1)(__VA_ARGS__)

//イテレータの最初から最後までを返す 例:sort(all(v))
#define all(x) (x).begin(),(x).end()
//上の逆順 例:sort(rall(v)) (降順にソートされる)
#define rall(x) (x).rbegin(),(x).rend()

//next_permutationでもらえる順に全部順列を返す 例:for(vi i:perm(v))
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

//sizeを int(ここ大事) で返す
#define sz(x) ((int)(x).size())

//boolを渡すとYesNoを出力する
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
/**************************************************/
int N,M;


int main(){
    input(N,M);
    vector<pii> ab(N);input(ab);
    set<pii> st;
    for(pii i:ab)st.insert(i);

    int ind=0;
    rep(i,1000){
        rep(j,1000){
            ind++;
            print(i,' ',j);
            if(ind==M){
                goto endloop;
            }
        }
    }
    endloop:
    print(N+1);
    vector<bool> gone(N,false);
    gone[0]=true;
    print(1,' ',1);

    int nx=ab[0].first,ny=ab[0].second;
    rep(i,1,N){
        int mi=INF;
        int to=-1;
        rep(j,N){
            if(gone[j])continue;
            int tmp=(nx-ab[j].first)*(nx-ab[j].first)+(ny-ab[j].second)*(ny-ab[j].second);
            if(tmp<mi){
                mi=tmp;
                to=j;
            }
        }
        gone[to]=true;
        nx=ab[to].first,ny=ab[to].second;
        print(1,' ',to+1);
    }
    print(1,' ',1);
}
0