結果

問題 No.5020 Averaging
ユーザー butsurizukibutsurizuki
提出日時 2024-02-21 14:29:03
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 954 ms / 1,000 ms
コード長 6,858 bytes
コンパイル時間 5,098 ms
コンパイル使用メモリ 300,380 KB
実行使用メモリ 6,676 KB
スコア 80,757,207
最終ジャッジ日時 2024-02-25 12:50:57
合計ジャッジ時間 54,244 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 929 ms
6,676 KB
testcase_01 AC 926 ms
6,676 KB
testcase_02 AC 905 ms
6,676 KB
testcase_03 AC 926 ms
6,676 KB
testcase_04 AC 905 ms
6,676 KB
testcase_05 AC 951 ms
6,676 KB
testcase_06 AC 954 ms
6,676 KB
testcase_07 AC 915 ms
6,676 KB
testcase_08 AC 932 ms
6,676 KB
testcase_09 AC 905 ms
6,676 KB
testcase_10 AC 926 ms
6,676 KB
testcase_11 AC 926 ms
6,676 KB
testcase_12 AC 905 ms
6,676 KB
testcase_13 AC 909 ms
6,676 KB
testcase_14 AC 904 ms
6,676 KB
testcase_15 AC 918 ms
6,676 KB
testcase_16 AC 953 ms
6,676 KB
testcase_17 AC 935 ms
6,676 KB
testcase_18 AC 937 ms
6,676 KB
testcase_19 AC 908 ms
6,676 KB
testcase_20 AC 914 ms
6,676 KB
testcase_21 AC 926 ms
6,676 KB
testcase_22 AC 936 ms
6,676 KB
testcase_23 AC 921 ms
6,676 KB
testcase_24 AC 928 ms
6,676 KB
testcase_25 AC 912 ms
6,676 KB
testcase_26 AC 905 ms
6,676 KB
testcase_27 AC 943 ms
6,676 KB
testcase_28 AC 917 ms
6,676 KB
testcase_29 AC 916 ms
6,676 KB
testcase_30 AC 936 ms
6,676 KB
testcase_31 AC 905 ms
6,676 KB
testcase_32 AC 909 ms
6,676 KB
testcase_33 AC 920 ms
6,676 KB
testcase_34 AC 903 ms
6,676 KB
testcase_35 AC 949 ms
6,676 KB
testcase_36 AC 944 ms
6,676 KB
testcase_37 AC 903 ms
6,676 KB
testcase_38 AC 906 ms
6,676 KB
testcase_39 AC 933 ms
6,676 KB
testcase_40 AC 932 ms
6,676 KB
testcase_41 AC 908 ms
6,676 KB
testcase_42 AC 922 ms
6,676 KB
testcase_43 AC 907 ms
6,676 KB
testcase_44 AC 926 ms
6,676 KB
testcase_45 AC 909 ms
6,676 KB
testcase_46 AC 907 ms
6,676 KB
testcase_47 AC 928 ms
6,676 KB
testcase_48 AC 945 ms
6,676 KB
testcase_49 AC 923 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include <sys/time.h>

using namespace std;

long long start_time;

void start_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  start_time=(tv.tv_sec*1000000+tv.tv_usec);
}

long long current_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  // cout << current_time-start_time << "(us)\n";
  return current_time-start_time;
}

unsigned long long xor128(){
  static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

using i128=__int128;
using pll=pair<long long,long long>;

i128 det(long long a,long long b,long long c,long long d){
  i128 l=a; l*=d;
  i128 r=b; r*=c;
  return (l-r);
}

vector<pll> convex_hull(vector<pll> P){
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    if(P.size()<=2){
        return P;
    }
    vector<pll> H,L,R;
    // sort(P.begin(),P.end());

    //下半分
    for(int i=0;i<P.size();i++){
        int j=L.size();
        while(j>=2 && det((L[j-1].first-L[j-2].first),(L[j-1].second-L[j-2].second),(P[i].first-L[j-2].first),(P[i].second-L[j-2].second))<=0){
            L.pop_back();
            j--;
        }
        L.push_back(P[i]);
    }

    //上半分
    for(int i=P.size()-1;i>=0;i--){
        int j=H.size();
        while(j>=2 && det((H[j-1].first-H[j-2].first),(H[j-1].second-H[j-2].second),(P[i].first-H[j-2].first),(P[i].second-H[j-2].second))<=0){
            H.pop_back();
            j--;
        }
        H.push_back(P[i]);
    }

    R=L;
    for(int i=1;i<H.size()-1;i++){
        R.push_back(H[i]);
    }

    return R;
}

pll f(pll a,pll b){
  return {(a.first+b.first)/2,(a.second+b.second)/2};
}

#define target 500000000000000000

bool jud(vector<pll> &P){
  int n=P.size();
  for(int i=0;i<n;i++){
    long long a=P[(i+1)%n].first-P[i].first;
    long long b=P[(i+1)%n].second-P[i].second;
    long long c=target-P[i].first;
    long long d=target-P[i].second;

    if(det(a,b,c,d) < 0){
      return false;
    }
  }
  return true;
}

void shrink(int tg,vector<pll> &p){
  for(int i=0;i<p.size();i++){
    p[i]=f(p[i],p[tg]);
  }
}

using pi=pair<int,int>;

vector<pi> gensuf(int remhd,vector<pll> p){
  int n=p.size();
  vector<int> id(n-1);
  for(int i=0;i<n-1;i++){
    p[i]=p[i+1];
    id[i]=i+1;
  }
  p.pop_back();
  vector<pi> res;

  vector<pair<pll,int>> ppi;
  for(int i=0;i<p.size();i++){
    ppi.push_back({p[i],id[i]});
  }
  sort(ppi.begin(),ppi.end());
  for(int i=0;i<p.size();i++){
    p[i]=ppi[i].first;
    id[i]=ppi[i].second;
  }

  for(int hd=0;hd<remhd;hd++){
    int tg=-1;
    i128 gp=1e37;
    for(int i=0;i<p.size();i++){
      vector<pll> up=p;
      shrink(i,up);
      vector<pll> htg;
      for(int j=0;j<p.size();j++){
        if(i==j){continue;}
        htg.push_back(up[j]);
      }
      vector<pll> ch=convex_hull(htg);
      if(jud(ch)){
        i128 gx=0,gy=0;
        for(auto &nx : ch){
          gx+=nx.first;
          gy+=nx.second;
        }
        gx/=ch.size();
        gy/=ch.size();
        i128 gd=(gx-target)*(gx-target)+(gy-target)*(gy-target);
        if(gp > gd){
          gp=gd;
          tg=i;
        }
      }
    }
    if(tg==-1){break;}

    shrink(tg,p);
    res.push_back({0,id[tg]});
    for(int i=tg;i<p.size();i++){
      p[i]=p[i+1];
      id[i]=id[i+1];
    }
    p.pop_back();
    id.pop_back();
  }

  reverse(res.begin(),res.end());
  return res;
}

void simu(vector<pi> &op,vector<pll> &p){
  for(auto &nx : op){
    p[nx.first]=f(p[nx.first],p[nx.second]);
    p[nx.second]=p[nx.first];
  }
}

long long eval(vector<pi> &op,vector<pll> p){
  simu(op,p);
  return max(abs(p[0].first-target),abs(p[0].second-target));
}

int main(){
  start_clock();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<pll> p(n);
  for(int i=0;i<n;i++){
    long long x,y;
    cin >> x >> y;
    p[i].first=x;
    p[i].second=y;
  }

  vector<pi> res;
  res=gensuf(50,p);

  vector<int> ex(n,0);
  for(int i=0;i<res.size();i++){
    ex[res[i].second]=1;
  }
  reverse(res.begin(),res.end());
  for(int i=1;i<n;i++){
    if(ex[i]==0){
      res.push_back({0,i});
    }
  }
  while(res.size()<50){
    res.push_back(res.back());
  }
  reverse(res.begin(),res.end());

  long long sc=eval(res,p);

  for(int att=0;;att++){
    if(current_clock()>100000){break;}
    for(int i=0;i<20;i++){
      for(int j=0;j<n;j++){
        for(int k=j+1;k<n;k++){
          int pj=res[i].first;
          int pk=res[i].second;
          res[i].first=j;
          res[i].second=k;
          long long csc=eval(res,p);
          if(sc>=csc){
            sc=csc;
          }
          else{
            res[i].first=pj;
            res[i].second=pk;
          }
        }
      }
    }

    for(int i=0;i<20;i++){
      for(int j=1;j<n;j++){
        int pf=res[i].first;
        int pj=res[i].second;
        res[i].first=0;
        res[i].second=j;
        long long csc=eval(res,p);
        if(sc>=csc){
          sc=csc;
        }
        else{
          res[i].first=pf;
          res[i].second=pj;
        }
      }
    }
  }

  for(int att=0;;att++){
    if(current_clock()>900000){break;}
    for(int i=0;i<15;i++){
      for(int j=i+1;j<15;j++){
        for(int k=1;k<n;k++){
          for(int l=1;l<n;l++){
            int pk=res[i].second;
            int pl=res[j].second;
            res[i].second=k;
            res[j].second=l;
            long long csc=eval(res,p);
            if(sc>=csc){
              sc=csc;
            }
            else{
              res[i].second=pk;
              res[j].second=pl;
            }
          }
        }
      }
    }

    for(int i=0;i<20;i++){
      for(int j=0;j<n;j++){
        for(int k=j+1;k<n;k++){
          int pj=res[i].first;
          int pk=res[i].second;
          res[i].first=j;
          res[i].second=k;
          long long csc=eval(res,p);
          if(sc>=csc){
            sc=csc;
          }
          else{
            res[i].first=pj;
            res[i].second=pk;
          }
        }
      }
    }

    for(int i=0;i<20;i++){
      for(int j=1;j<n;j++){
        int pf=res[i].first;
        int pj=res[i].second;
        res[i].first=0;
        res[i].second=j;
        long long csc=eval(res,p);
        if(sc>=csc){
          sc=csc;
        }
        else{
          res[i].first=pf;
          res[i].second=pj;
        }
      }
    }
  }

  cout << res.size() << "\n";
  for(auto &nx : res){
    cout << nx.first+1 << " " << nx.second+1 << "\n";
  }

  //simu(res,p);
  //for(auto &nx : p){
  //  long long ox=nx.first;
  //  long long oy=nx.second;
  //  cout << ox << " " << oy << "\n";
  //}
  return 0;
}
0