結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-20 15:41:16 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 217 ms / 1,000 ms |
コード長 | 2,440 bytes |
コンパイル時間 | 4,638 ms |
コンパイル使用メモリ | 299,040 KB |
実行使用メモリ | 10,240 KB |
スコア | 30,398,532 |
最終ジャッジ日時 | 2024-02-25 12:45:11 |
合計ジャッジ時間 | 17,337 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 213 ms
10,240 KB |
testcase_01 | AC | 213 ms
10,240 KB |
testcase_02 | AC | 212 ms
10,240 KB |
testcase_03 | AC | 212 ms
10,240 KB |
testcase_04 | AC | 211 ms
10,112 KB |
testcase_05 | AC | 211 ms
10,240 KB |
testcase_06 | AC | 211 ms
10,240 KB |
testcase_07 | AC | 213 ms
10,240 KB |
testcase_08 | AC | 210 ms
10,240 KB |
testcase_09 | AC | 208 ms
10,240 KB |
testcase_10 | AC | 215 ms
10,240 KB |
testcase_11 | AC | 216 ms
10,240 KB |
testcase_12 | AC | 214 ms
10,240 KB |
testcase_13 | AC | 212 ms
10,112 KB |
testcase_14 | AC | 213 ms
10,240 KB |
testcase_15 | AC | 211 ms
10,240 KB |
testcase_16 | AC | 210 ms
10,240 KB |
testcase_17 | AC | 215 ms
10,240 KB |
testcase_18 | AC | 211 ms
10,240 KB |
testcase_19 | AC | 215 ms
10,240 KB |
testcase_20 | AC | 217 ms
10,240 KB |
testcase_21 | AC | 213 ms
10,240 KB |
testcase_22 | AC | 215 ms
10,240 KB |
testcase_23 | AC | 213 ms
10,240 KB |
testcase_24 | AC | 212 ms
10,240 KB |
testcase_25 | AC | 210 ms
10,240 KB |
testcase_26 | AC | 214 ms
10,240 KB |
testcase_27 | AC | 213 ms
10,240 KB |
testcase_28 | AC | 213 ms
10,240 KB |
testcase_29 | AC | 213 ms
10,240 KB |
testcase_30 | AC | 213 ms
10,240 KB |
testcase_31 | AC | 215 ms
10,240 KB |
testcase_32 | AC | 214 ms
10,240 KB |
testcase_33 | AC | 212 ms
10,240 KB |
testcase_34 | AC | 212 ms
10,240 KB |
testcase_35 | AC | 209 ms
10,240 KB |
testcase_36 | AC | 213 ms
10,240 KB |
testcase_37 | AC | 213 ms
10,240 KB |
testcase_38 | AC | 214 ms
10,112 KB |
testcase_39 | AC | 215 ms
10,240 KB |
testcase_40 | AC | 211 ms
10,240 KB |
testcase_41 | AC | 210 ms
10,240 KB |
testcase_42 | AC | 209 ms
10,240 KB |
testcase_43 | AC | 214 ms
10,240 KB |
testcase_44 | AC | 213 ms
10,240 KB |
testcase_45 | AC | 212 ms
10,240 KB |
testcase_46 | AC | 210 ms
10,240 KB |
testcase_47 | AC | 209 ms
10,240 KB |
testcase_48 | AC | 215 ms
10,240 KB |
testcase_49 | AC | 213 ms
10,240 KB |
ソースコード
#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; long long eval(Game &g){ long long g1=abs(g.card[0].first-target); long long g2=abs(g.card[0].second-target); long long g3=abs(g.card[0].first-g.card[0].second); return -max(g1,g2); } #define BSIZE 3000 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}; long long rr=-8e18; Game res=inig; for(int tr=0;tr<50;tr++){ vector<Game> ng; priority_queue<pl,vector<pl>,greater<pl>> pq; for(auto &nx : gs){ for(int i=0;i<n;i++){ if(i!=0){break;} 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); long long 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; }