結果
問題 |
No.8011 品物の並び替え (Extra)
|
ユーザー |
![]() |
提出日時 | 2020-08-03 18:13:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,728 ms / 5,000 ms |
コード長 | 1,429 bytes |
コンパイル時間 | 7,236 ms |
コンパイル使用メモリ | 257,108 KB |
最終ジャッジ日時 | 2025-01-12 13:43:18 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 |
コンパイルメッセージ
main.cpp: In function 'void solve()': main.cpp:34:31: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = int*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations] 34 | random_shuffle(cur,cur+N); | ~~~~~~~~~~~~~~^~~~~~~~~~~ In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/algorithm:61, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:65, from main.cpp:1: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algo.h:4541:5: note: declared here 4541 | random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) | ^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<to;x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,M; int mat[51][51]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; while(M--) { cin>>x>>y>>r; mat[x][y]=r; } ll ma=-1; int cur[51]; int pat[51]; FOR(i,N) cur[i]=i; srand(time(NULL)); FOR(i,400000) { random_shuffle(cur,cur+N); ll tot=0; FOR(y,N) FOR(x,y) tot+=mat[cur[x]][cur[y]]; FOR(j,100) { x=rand()%N; y=rand()%N; if(x==y) continue; if(x>y) swap(x,y); int diff=mat[cur[y]][cur[x]]-mat[cur[x]][cur[y]]; for(r=x+1;r<=y-1;r++) diff+=mat[cur[r]][cur[x]]-mat[cur[x]][cur[r]]+mat[cur[y]][cur[r]]-mat[cur[r]][cur[y]]; if(diff>0) { tot += diff; swap(cur[x],cur[y]); if(tot>ma) { ma=tot; FOR(x,N) pat[x]=cur[x]; } } } } _P("%d\n",ma); FOR(i,N) _P("%d%c",pat[i],(i==N-1)?'\n':' '); } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }