結果
問題 | 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 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; }