結果
問題 | No.8011 品物の並び替え (Extra) |
ユーザー | mayoko_ |
提出日時 | 2015-05-04 15:18:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,277 bytes |
コンパイル時間 | 1,698 ms |
コンパイル使用メモリ | 162,448 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 18:55:01 |
合計ジャッジ時間 | 36,323 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4,802 ms
5,248 KB |
testcase_01 | AC | 4,802 ms
5,376 KB |
testcase_02 | AC | 4,802 ms
5,376 KB |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | AC | 4,801 ms
5,376 KB |
testcase_06 | AC | 4,802 ms
5,376 KB |
testcase_07 | RE | - |
testcase_08 | AC | 4,801 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; int item1[55], item2[55], score[55]; int mat[55][55]; int N, M; // 乱数生成 unsigned int randxor() { static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; unsigned int t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } int getScore(const vector<int>& seq) { int ret = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { ret += mat[seq[i]][seq[j]]; } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; for (int i = 0; i < M; i++) { cin >> item1[i] >> item2[i] >> score[i]; mat[item1[i]][item2[i]] = score[i]; } vector<int> currentSeq(N); for (int i = 0; i < N; i++) currentSeq[i] = i; vector<int> bestSeq = currentSeq; int bestScore = getScore(currentSeq); int currentScore = bestScore; auto start = std::chrono::system_clock::now(); ll restTime = 0; int timeCnt = 0; while (1) { //for (int i = 0 ; i < N; i++) cout << currentSeq[i] << " "; //cout << endl; if (timeCnt >= 100) { timeCnt = 0; auto now = std::chrono::system_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now-start); restTime = duration.count(); if (restTime >= 4800) break; } timeCnt++; int r = randxor() % N; int q = randxor() % N; bool FORCE_MOVE = randxor()%100000 < (4800-restTime); swap(currentSeq[r], currentSeq[q]); int nextScore = getScore(currentSeq); if (nextScore > currentScore || FORCE_MOVE) { currentScore = nextScore; } else { swap(currentSeq[r], currentSeq[q]); } if (bestScore < currentScore) { bestSeq = currentSeq; bestScore = currentScore; } } cout << bestScore << endl; for (int i = 0; i < N; i++) { cout << bestSeq[i] << endl; } return 0; }