結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-20 14:33:51 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,296 bytes |
コンパイル時間 | 5,129 ms |
コンパイル使用メモリ | 298,172 KB |
実行使用メモリ | 6,548 KB |
スコア | 0 |
最終ジャッジ日時 | 2024-02-25 12:43:55 |
合計ジャッジ時間 | 66,775 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | TLE | - |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | TLE | - |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | TLE | - |
testcase_45 | TLE | - |
testcase_46 | TLE | - |
testcase_47 | TLE | - |
testcase_48 | TLE | - |
testcase_49 | TLE | - |
ソースコード
#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 1000 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; }