結果
| 問題 | No.5020 Averaging |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-05-05 00:00:35 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 903 ms / 1,000 ms |
| コード長 | 7,118 bytes |
| 記録 | |
| コンパイル時間 | 2,197 ms |
| コンパイル使用メモリ | 346,552 KB |
| 実行使用メモリ | 7,972 KB |
| スコア | 91,569,227 |
| 最終ジャッジ日時 | 2026-05-05 00:01:28 |
| 合計ジャッジ時間 | 50,063 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmin_ref(T &a,const T &b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::steady_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::steady_clock::now();
}
void snap(){
start=chrono::steady_clock::now();
}
int get_ms(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
mt19937 mt;
uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){ //[l,r)
assert(l<r);
return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){ //[0.0,1.0]
return mt()*one_div_mt_max;
}
double rand_double(double l,double r){ //[l,r]
return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
assert(!v.empty());
return v[rand_int(len(v))];
}
template<class T> void add(vector<T> &a,vector<T> b){
for(auto i:b) a.push_back(i);
}
template<class SA_State> SA_State SA(const SA_State &first_state,int limit_ms,double start_temp,double end_temp=0.0){
SA_State state=first_state,best_state=state;
int loop_cnt=0,accept_cnt=0,update_cnt=0;
int ms=0;
double temp=start_temp;
Timer::snap();
while(true){
if((loop_cnt&63)==63){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
//double t=(double)ms/limit_ms;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=pow(start_temp,1-t)*pow(end_temp,t);
}
loop_cnt++;
double accept_diff=log(rand_double())*temp;
bool accepted=state.modify(accept_diff);
if(accepted){
accept_cnt++;
if(state.score<best_state.score){
best_state=state;
//cerr << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
update_cnt++;
}
}
}
//cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
return best_state;
};
constexpr int N=45;
array<ll,N> A,B;
constexpr ll L=5e17,M=1e18;
ll calc_score(const vector<int> &ord){
array<ll,N> a=A,b=B;
for(auto e:ord){
a[0]=a[e]=(a[0]+a[e])/2;
b[0]=b[e]=(b[0]+b[e])/2;
}
return max(abs(L-a[0]),abs(L-b[0]));
}
namespace Solver{
struct State{
vector<int> ord;
double score=0;
State():ord(N-1){
rep(i,N-1){
ord[i]=1+i;
}
score=calc_score();
}
double calc_score() const{
return log10(::calc_score(ord)+1);
}
bool modify(double accept_diff){
int a=rand_int(N-1),b=rand_int(N-1);
swap(ord[a],ord[b]);
double new_score=calc_score();
if(accept_diff<=score-new_score){
score=new_score;
return true;
}else{
swap(ord[a],ord[b]);
return false;
}
}
};
void dfs(int k,ll x,ll y,vector<int> &cand,vector<int> &used,vector<int> &ord,ll &best_score,vector<int> &best_ord){
static int loop=0;
static bool fin=false;
if(fin) return;
loop++;
if((loop&1023)==0){
if(900<Timer::get_ms()) fin=true;
}
if(k==-1){
ll now_score=calc_score(ord);
if(chmin(best_score,now_score)){
best_ord=ord;
}
return;
}
rep(i,len(cand)){
if(used[i]) continue;
ll nx=x+(A[cand[i]]>>(N-1-k));
ll ny=y+(B[cand[i]]>>(N-1-k));
if(10000<nx-L) continue;
if(nx+(M>>(N-1-k))-L<-10000) continue;
if(10000<ny-L) continue;
if(ny+(M>>(N-1-k))-L<-10000) continue;
used[i]=true;
ord[k]=cand[i];
dfs(k-1,nx,ny,cand,used,ord,best_score,best_ord);
ord[k]=-1;
used[i]=false;
}
}
void solve(){
State state;
state=SA<State>(state,100,0.2,0.2);
vector<int> ord=state.ord;
ll best_score=calc_score(ord);
vector<int> best_ord=ord;
replr(s,1,N-1){
ll x=0,y=0;
replr(i,s,N-1){
x+=A[ord[i]]>>(N-1-i);
y+=B[ord[i]]>>(N-1-i);
}
vector<int> cand;
vector<int> now_ord=ord;
rep(i,s){
cand.push_back(ord[i]);
now_ord[i]=-1;
}
vector<int> used(len(cand),false);
dfs(s-1,x,y,cand,used,now_ord,best_score,best_ord);
}
cout << len(best_ord) << '\n';
for(auto e:best_ord){
cout << 1 << ' ' << e+1 << '\n';
}
cerr << (int)floor(2000000-100000*log10(best_score+1)) << ' ' << Timer::get_ms() << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int n;
cin >> n;
assert(n==N);
rep(i,N) cin >> A[i] >> B[i];
Solver::solve();
exit(0);
}