結果

問題 No.8011 品物の並び替え (Extra)
ユーザー tottoripaper
提出日時 2015-05-04 00:22:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4,528 ms / 5,000 ms
コード長 1,856 bytes
コンパイル時間 867 ms
コンパイル使用メモリ 84,240 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 18:30:17
合計ジャッジ時間 16,610 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:67:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%d %d %d", &list[i][0], &list[i][1], &list[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int evaluate()’:
main.cpp:43:9: warning: ‘b’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |         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