結果

問題 No.8011 品物の並び替え (Extra)
コンテスト
ユーザー tottoripaper
提出日時 2015-05-04 00:22:14
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,856 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 401 ms
コンパイル使用メモリ 87,840 KB
最終ジャッジ日時 2026-03-27 03:51:09
合計ジャッジ時間 703 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:81:12: error: 'clock' was not declared in this scope
   81 |     while (clock() / (double)(CLOCKS_PER_SEC) < 4.50){
      |            ^~~~~
main.cpp:8:1: note: 'clock' is defined in header '<ctime>'; this is probably fixable by adding '#include <ctime>'
    7 | #include <functional>
  +++ |+#include <ctime>
    8 | #include <vector>
main.cpp:81:31: error: 'CLOCKS_PER_SEC' was not declared in this scope
   81 |     while (clock() / (double)(CLOCKS_PER_SEC) < 4.50){
      |                               ^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

// 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