結果

問題 No.8011 品物の並び替え (Extra)
ユーザー mayoko_mayoko_
提出日時 2015-05-04 00:19:01
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,284 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 162,672 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 18:27:20
合計ジャッジ時間 36,001 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,802 ms
5,248 KB
testcase_01 AC 4,801 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,801 ms
5,376 KB
testcase_07 RE -
testcase_08 AC 4,801 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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()%10000 < (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;
}
0