結果

問題 No.3011 品物の並び替え (Extra)
ユーザー tottoripapertottoripaper
提出日時 2015-05-04 00:22:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4,524 ms / 5,000 ms
コード長 1,856 bytes
コンパイル時間 2,042 ms
コンパイル使用メモリ 82,856 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-19 06:15:53
合計ジャッジ時間 47,110 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,519 ms
4,380 KB
testcase_01 AC 4,519 ms
4,384 KB
testcase_02 AC 4,521 ms
4,380 KB
testcase_03 AC 4,519 ms
4,380 KB
testcase_04 AC 4,519 ms
4,380 KB
testcase_05 AC 4,522 ms
4,380 KB
testcase_06 AC 4,524 ms
4,380 KB
testcase_07 AC 4,519 ms
4,376 KB
testcase_08 AC 4,519 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int evaluate()’:
main.cpp:43:9: warning: ‘b’ may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(a < b){point += list[i][2];}
         ^~
main.cpp:43:9: warning: ‘a’ may be used uninitialized in this function [-Wmaybe-uninitialized]

ソースコード

diff # 

// Wrongri-La Shower

#include <cstdio>
#include <random>
#include <array>
#include <algorithm>
#include <functional>
#include <vector>

int N, M;
int list[3000][3];

int point = 0;
std::vector<int> v, best;

template <typename T>
std::function<T()> randomR(
    T lb, // ^ 下限
    T ub  // ^ 上限
){
    std::random_device rd;
    std::array<T, 10> seeds;
    std::generate(seeds.begin(), seeds.end(), std::ref(rd));

    std::seed_seq seq(seeds.begin(), seeds.end());
    return std::bind(std::uniform_int_distribution<T>(lb, ub),
                     std::mt19937(seq));
}

int evaluate(){
    int point = 0;
    
    for(int i=0;i<M;i++){
        int a, b;
        for(int j=0;j<N;j++){
            if(v[j] == list[i][0]){
                a = j;
            }else if(v[j] == list[i][1]){
                b = j;
            }
        }

        if(a < b){point += list[i][2];}
    }

    return point;
}

std::function<int()> choose;

void change(){
    int a = choose(), b = choose();
    if(a == b){return;}

    std::vector<int> u(v.begin(), v.end());
    std::swap(v[a], v[b]);
    int p = evaluate();
    if(p > point){
        point = p;
        std::copy(v.begin(), v.end(), best.begin());
    }else{
        v = std::move(u);
    }
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i=0;i<M;i++){
        scanf("%d %d %d", &list[i][0], &list[i][1], &list[i][2]);
    }

    v.resize(N);
    best.resize(N);    
    choose = randomR(0, N-1);
    
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());
    point = evaluate();
    std::copy(v.begin(), v.end(), best.begin());
    
    while (clock() / (double)(CLOCKS_PER_SEC) < 4.50){
        change();
    }

    printf("%d\n", point);
    for(int i=0;i<best.size();i++){
        printf("%d%c", best[i], " \n"[i+1==best.size()]);
    }
    puts("252521");
}
0