結果
問題 | No.5020 Averaging |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 500using 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;}