結果

問題 No.5020 Averaging
ユーザー butsurizuki
提出日時 2024-02-20 14:39:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 612 ms / 1,000 ms
コード長 2,295 bytes
コンパイル時間 5,333 ms
コンパイル使用メモリ 298,012 KB
実行使用メモリ 6,676 KB
スコア 24,278,744
最終ジャッジ日時 2024-02-25 12:43:59
合計ジャッジ時間 37,689 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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;
}
using pl=pair<long long,long long>;
long long target=500000000000000000;
double score(pl a){
long long mg=max(abs(a.first-target),abs(a.second-target));
return 1.0-0.05*log10(mg+1);
}
pl f(pl a,pl b){
return {(a.first+b.first)/2,(a.second+b.second)/2};
}
typedef struct{
vector<pl> card;
vector<int> hand;
}Game;
double eval(Game &g){
double x=0.0;
x=score(g.card[0]);
return x;
}
#define BSIZE 500
using pdi=pair<double,int>;
int main(){
start_clock();
int n;
cin >> n;
Game inig;
inig.card.resize(n);
for(auto &nx : inig.card){
cin >> nx.first >> nx.second;
}
inig.hand.clear();
vector<Game> gs={inig};
double rr=-100.0;
Game res=inig;
for(int tr=0;tr<50;tr++){
vector<Game> ng;
priority_queue<pdi,vector<pdi>,greater<pdi>> pq;
for(auto &nx : gs){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
pl ci=nx.card[i];
pl cj=nx.card[j];
pl ck=f(ci,cj);
nx.card[i]=ck;
nx.card[j]=ck;
nx.hand.push_back((i<<6)+j);
double ce=eval(nx);
if(rr<ce){
rr=ce;
res=nx;
}
if(ng.size()<BSIZE){
pq.push({ce,ng.size()});
ng.push_back(nx);
}
else if(pq.top().first < ce){
pdi od=pq.top();pq.pop();
od.first=ce;
pq.push(od);
ng[od.second]=nx;
}
nx.card[i]=ci;
nx.card[j]=cj;
nx.hand.pop_back();
}
}
}
gs=ng;
}
cout << res.hand.size() << "\n";
for(auto &nx : res.hand){
cout << (nx/64)+1 << " " << (nx%64)+1 << "\n";
}
//for(auto &nx : res.card){
// cout << nx.first << " " << nx.second << "\n";
//}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0