SuperCon2013 本選
SuperCon2013 本選に行ってきました。
4位でした。実力は出せたものの詰めが甘いです。
解法は主催者が想定していた通りな感じです。
解法
- がんばって逆にたどるだけ
- GK表とかいう粒子の衝突が起こった時の次の粒子の移動方向の表の変な性質はまったく使っていない。
- GK表は使いにくいので作り替えたのを埋め込んだ
- はじめCPUのプログラムを作ったときにGPUに書き換えやすいように書いたのがよかったのではないかと思った。
- 極力GPUへのデータ転送回数を少なくした。
- 隣接格子点の座標をはじめにCPUで求めておいて配列に格納しGPUでdivergent分岐をしないようにしたら6秒ぐらいはやくなった。
- コードの最初にcudaDeviceSynchronize()を入れるとなぜか4~5秒もはやくなって謎
以下提出したコード（多少編集しました）
/******************************************************************* スーパーコン１３の本選課題 入出力用テンプレート 名称 sc13_template.c by T. Yamazaki, O. Watanabe, and T. Endo, Aug. 15, 2013 version 130815-2000 *********************************************************************/ /********* テンプレート用 (1) ここから **********/ #include<stdio.h> #include<stdlib.h> #include<time.h> #include<sys/time.h> //------------ 各種定数（上界値） #define MAXN 500 // 空間の最大サイズ #define MAXM 4000 // １色あたりの星の最大数( 星の最大数は 3 * MAXM ) #define MAXT 5000 // 最大予測経過時間 #define MAXK 250 // Ａ群の最大数 #define MAXL 100 // Ｂ群の最大数 //------------ 遷移ルールのインクルード #include"transition_rule.h" /* #define TRANSITION_RULE_NUM 255 // 遷移ルールの数 struct TransitionRule { int id; // 遷移ルールid ( 普通は使用せず ) int length; // pattern, nextの長さ( 衝突している星の数 ) int pattern[ 8 ]; // 衝突している星の向きの集合を表す列 int next[ 8 ]; // 衝突後の各星の向き( 衝突前に向きが pattern[ i ] だった星は衝突後の向きは next[ i ] になる ) }; TransitionRule transition_rules[ TRANSITION_RULE_NUM ]; // 全ての遷移ルールの集合を表す列 // */ //------------ 入出力用構造体 typedef struct Star_{ int x; // x座標 int y; // y座標 int dir; // 移動方向 int color; // 色 } Star; //------------ 入出力用変数 int N; // 空間のサイズ( 幅, 高さ ) int M; // １色あたりの星の数( 星の合計数は 3 * M ) int T; // Ａ群とＢ群の間の予測経過時間 int K; // Ａ群のサイズ int L; // Ｂ群のサイズ Star A[ MAXK ][ 3 * MAXM ]; // Ａ群を表すデータ Star B[ MAXL ][ 3 * MAXM ]; // Ｂ群を表すデータ int answer[ MAXL ]; // 出力用 // answer[ i ] には B[ i ] の過去であるようなＡ群のインデックスを格納する //------------ 入出力用関数 // 入力用 void input() { int i, c, j; scanf( " %d %d %d %d %d", &N, &M, &T, &K, &L ); for( i = 0; i < K; i++ ){ for( c = 0; c < 3; c++ ){ for( j = 0; j < M; j++ ){ Star *cur = &A[ i ][ c * M + j ]; scanf( " %d %d %d", &cur->x, &cur->y, &cur->dir ); cur->color = c; } } } for( i = 0; i < L; i++ ){ for( c = 0; c < 3; c++ ){ for( j = 0; j < M; j++ ){ Star *cur = &B[ i ][ c * M + j ]; scanf( " %d %d %d", &cur->x, &cur->y, &cur->dir ); cur->color = c; } } } } // 出力用 void output() { int i; for( i = 0; i < L; i++ ){ if( i > 0 ){ printf( " " ); } printf( "%d", answer[ i ] ); } printf( "\n" ); } /********* テンプレート用 (1) ここまで **********/ /********* 以下に各自で使うプログラムの変数や手続きの定義を書く **********/ #include <string.h> #define EMPTY -1 #define BIT(a,k) (a + (1 << k)) //a の k 番目の BIT を 1 にする #define MAXN_ 512 // [t][x][y][k] #define IDXN4(i,x,y,k,n) ((i&1)*(n)*(n)*8 + (x)*(n)*8 + (y)*8 + (k)) // [t][x][y] #define IDXN3(i,x,y,n) ((i&1)*(n)*(n) + (x)*(n) + (y)) char univ_n[2 * MAXN_ * MAXN_]; //宇宙[i][j]に存在する星の個数 __device__ char univ_vD[2 * MAXN_ * MAXN_ * 8]; // 0~7...方向 EMPTY...星なし __device__ char univ_cD[2 * MAXN_ * MAXN_ * 8]; // 0,1,2...色 EMPTY...星なし __device__ char univ_nD[2 * MAXN_ * MAXN_]; //宇宙[i][j]に存在する星の個数 int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; int dy[8] = { 1, 1, 1, 0, -1, -1, -1, 0}; __device__ int dxD[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; __device__ int dyD[8] = { 1, 1, 1, 0, -1, -1, -1, 0}; int adjx[MAXN][8]; int adjy[MAXN][8]; __device__ int adjxD[MAXN][8]; __device__ int adjyD[MAXN][8]; void *adjxD_p, *adjyD_p; __device__ Star BD[MAXL][3 * MAXM]; void *BD_p; #define IDXN_UA(u,x,y,N) ((u)*(N)*(N) + (x)*(N) + y) #define IDN_UA(u,x,y) ((u)*MAXN*MAXN + (x)*MAXN + y) char univA_v[MAXK * MAXN * MAXN]; // 0~7...方向 EMPTY...星なし 宇宙 A char univA_c[MAXK * MAXN * MAXN]; // 0,1,2...色 EMPTY...星なし 宇宙 A __device__ char univA_vD[MAXK * MAXN * MAXN]; // 0~7...方向 EMPTY...星なし 宇宙 A __device__ char univA_cD[MAXK * MAXN * MAXN]; // 0,1,2...色 EMPTY...星なし 宇宙 A __device__ TransitionRule new_transition_rulesD[256] = { { 0, 0, {0, 0, 0, 0, 0, 0, 0, 0, }, {4, 4, 4, 4, 4, 4, 4, 4, }}, { 1, 1, {0, 0, 0, 0, 0, 0, 0, 0, }, {0, 4, 4, 4, 4, 4, 4, 4, }}, { 2, 1, {1, 0, 0, 0, 0, 0, 0, 0, }, {1, 4, 4, 4, 4, 4, 4, 4, }}, { 3, 2, {0, 1, 0, 0, 0, 0, 0, 0, }, {1, 0, 4, 4, 4, 4, 4, 4, }}, { 4, 1, {2, 0, 0, 0, 0, 0, 0, 0, }, {2, 4, 4, 4, 4, 4, 4, 4, }}, { 5, 2, {0, 2, 0, 0, 0, 0, 0, 0, }, {2, 0, 4, 4, 4, 4, 4, 4, }}, { 6, 2, {1, 2, 0, 0, 0, 0, 0, 0, }, {2, 1, 4, 4, 4, 4, 4, 4, }}, { 7, 3, {0, 1, 2, 0, 0, 0, 0, 0, }, {2, 1, 0, 4, 4, 4, 4, 4, }}, { 8, 1, {3, 0, 0, 0, 0, 0, 0, 0, }, {3, 4, 4, 4, 4, 4, 4, 4, }}, { 9, 2, {0, 3, 0, 0, 0, 0, 0, 0, }, {3, 0, 4, 4, 4, 4, 4, 4, }}, { 10, 2, {1, 3, 0, 0, 0, 0, 0, 0, }, {3, 1, 4, 4, 4, 4, 4, 4, }}, { 11, 3, {0, 1, 3, 0, 0, 0, 0, 0, }, {3, 1, 0, 4, 4, 4, 4, 4, }}, { 12, 2, {2, 3, 0, 0, 0, 0, 0, 0, }, {3, 2, 4, 4, 4, 4, 4, 4, }}, { 13, 3, {0, 2, 3, 0, 0, 0, 0, 0, }, {3, 2, 0, 4, 4, 4, 4, 4, }}, { 14, 3, {1, 2, 3, 0, 0, 0, 0, 0, }, {3, 2, 1, 4, 4, 4, 4, 4, }}, { 15, 4, {0, 1, 2, 3, 0, 0, 0, 0, }, {3, 1, 2, 0, 4, 4, 4, 4, }}, { 16, 1, {4, 0, 0, 0, 0, 0, 0, 0, }, {4, 4, 4, 4, 4, 4, 4, 4, }}, { 17, 2, {0, 4, 0, 0, 0, 0, 0, 0, }, {4, 0, 4, 4, 4, 4, 4, 4, }}, { 18, 2, {1, 4, 0, 0, 0, 0, 0, 0, }, {4, 1, 4, 4, 4, 4, 4, 4, }}, { 19, 3, {0, 1, 4, 0, 0, 0, 0, 0, }, {4, 1, 0, 4, 4, 4, 4, 4, }}, { 20, 2, {2, 4, 0, 0, 0, 0, 0, 0, }, {4, 2, 4, 4, 4, 4, 4, 4, }}, { 21, 3, {0, 2, 4, 0, 0, 0, 0, 0, }, {4, 2, 0, 4, 4, 4, 4, 4, }}, { 22, 3, {1, 2, 4, 0, 0, 0, 0, 0, }, {4, 2, 1, 4, 4, 4, 4, 4, }}, { 23, 4, {0, 1, 2, 4, 0, 0, 0, 0, }, {4, 1, 2, 0, 4, 4, 4, 4, }}, { 24, 2, {3, 4, 0, 0, 0, 0, 0, 0, }, {4, 3, 4, 4, 4, 4, 4, 4, }}, { 25, 3, {0, 3, 4, 0, 0, 0, 0, 0, }, {4, 3, 0, 4, 4, 4, 4, 4, }}, { 26, 3, {1, 3, 4, 0, 0, 0, 0, 0, }, {4, 3, 1, 4, 4, 4, 4, 4, }}, { 27, 4, {0, 1, 3, 4, 0, 0, 0, 0, }, {4, 1, 3, 0, 4, 4, 4, 4, }}, { 28, 3, {2, 3, 4, 0, 0, 0, 0, 0, }, {4, 3, 2, 4, 4, 4, 4, 4, }}, { 29, 4, {0, 2, 3, 4, 0, 0, 0, 0, }, {4, 2, 3, 0, 4, 4, 4, 4, }}, { 30, 4, {1, 2, 3, 4, 0, 0, 0, 0, }, {4, 2, 3, 1, 4, 4, 4, 4, }}, { 31, 5, {0, 1, 2, 3, 4, 0, 0, 0, }, {4, 1, 2, 3, 0, 4, 4, 4, }}, { 32, 1, {5, 0, 0, 0, 0, 0, 0, 0, }, {5, 4, 4, 4, 4, 4, 4, 4, }}, { 33, 2, {0, 5, 0, 0, 0, 0, 0, 0, }, {5, 0, 4, 4, 4, 4, 4, 4, }}, { 34, 2, {1, 5, 0, 0, 0, 0, 0, 0, }, {5, 1, 4, 4, 4, 4, 4, 4, }}, { 35, 3, {0, 1, 5, 0, 0, 0, 0, 0, }, {0, 5, 1, 4, 4, 4, 4, 4, }}, { 36, 2, {2, 5, 0, 0, 0, 0, 0, 0, }, {5, 2, 4, 4, 4, 4, 4, 4, }}, { 37, 3, {0, 2, 5, 0, 0, 0, 0, 0, }, {4, 6, 1, 4, 4, 4, 4, 4, }}, { 38, 3, {1, 2, 5, 0, 0, 0, 0, 0, }, {5, 2, 1, 4, 4, 4, 4, 4, }}, { 39, 4, {0, 1, 2, 5, 0, 0, 0, 0, }, {0, 5, 2, 1, 4, 4, 4, 4, }}, { 40, 2, {3, 5, 0, 0, 0, 0, 0, 0, }, {5, 3, 4, 4, 4, 4, 4, 4, }}, { 41, 3, {0, 3, 5, 0, 0, 0, 0, 0, }, {0, 5, 3, 4, 4, 4, 4, 4, }}, { 42, 3, {1, 3, 5, 0, 0, 0, 0, 0, }, {5, 3, 1, 4, 4, 4, 4, 4, }}, { 43, 4, {0, 1, 3, 5, 0, 0, 0, 0, }, {3, 5, 0, 1, 4, 4, 4, 4, }}, { 44, 3, {2, 3, 5, 0, 0, 0, 0, 0, }, {5, 3, 2, 4, 4, 4, 4, 4, }}, { 45, 4, {0, 2, 3, 5, 0, 0, 0, 0, }, {3, 2, 0, 5, 4, 4, 4, 4, }}, { 46, 4, {1, 2, 3, 5, 0, 0, 0, 0, }, {5, 2, 3, 1, 4, 4, 4, 4, }}, { 47, 5, {0, 1, 2, 3, 5, 0, 0, 0, }, {0, 5, 2, 3, 1, 4, 4, 4, }}, { 48, 2, {4, 5, 0, 0, 0, 0, 0, 0, }, {5, 4, 4, 4, 4, 4, 4, 4, }}, { 49, 3, {0, 4, 5, 0, 0, 0, 0, 0, }, {4, 0, 5, 4, 4, 4, 4, 4, }}, { 50, 3, {1, 4, 5, 0, 0, 0, 0, 0, }, {5, 4, 1, 4, 4, 4, 4, 4, }}, { 51, 4, {0, 1, 4, 5, 0, 0, 0, 0, }, {4, 5, 0, 1, 4, 4, 4, 4, }}, { 52, 3, {2, 4, 5, 0, 0, 0, 0, 0, }, {5, 4, 2, 4, 4, 4, 4, 4, }}, { 53, 4, {0, 2, 4, 5, 0, 0, 0, 0, }, {4, 2, 0, 5, 4, 4, 4, 4, }}, { 54, 4, {1, 2, 4, 5, 0, 0, 0, 0, }, {5, 2, 4, 1, 4, 4, 4, 4, }}, { 55, 5, {0, 1, 2, 4, 5, 0, 0, 0, }, {4, 5, 2, 0, 1, 4, 4, 4, }}, { 56, 3, {3, 4, 5, 0, 0, 0, 0, 0, }, {5, 4, 3, 4, 4, 4, 4, 4, }}, { 57, 4, {0, 3, 4, 5, 0, 0, 0, 0, }, {4, 3, 0, 5, 4, 4, 4, 4, }}, { 58, 4, {1, 3, 4, 5, 0, 0, 0, 0, }, {5, 3, 4, 1, 4, 4, 4, 4, }}, { 59, 5, {0, 1, 3, 4, 5, 0, 0, 0, }, {4, 5, 3, 0, 1, 4, 4, 4, }}, { 60, 4, {2, 3, 4, 5, 0, 0, 0, 0, }, {5, 3, 4, 2, 4, 4, 4, 4, }}, { 61, 5, {0, 2, 3, 4, 5, 0, 0, 0, }, {4, 2, 3, 0, 5, 4, 4, 4, }}, { 62, 5, {1, 2, 3, 4, 5, 0, 0, 0, }, {5, 2, 3, 4, 1, 4, 4, 4, }}, { 63, 6, {0, 1, 2, 3, 4, 5, 0, 0, }, {4, 5, 2, 3, 0, 1, 4, 4, }}, { 64, 1, {6, 0, 0, 0, 0, 0, 0, 0, }, {6, 4, 4, 4, 4, 4, 4, 4, }}, { 65, 2, {0, 6, 0, 0, 0, 0, 0, 0, }, {6, 0, 4, 4, 4, 4, 4, 4, }}, { 66, 2, {1, 6, 0, 0, 0, 0, 0, 0, }, {6, 1, 4, 4, 4, 4, 4, 4, }}, { 67, 3, {0, 1, 6, 0, 0, 0, 0, 0, }, {0, 6, 1, 4, 4, 4, 4, 4, }}, { 68, 2, {2, 6, 0, 0, 0, 0, 0, 0, }, {6, 2, 4, 4, 4, 4, 4, 4, }}, { 69, 3, {0, 2, 6, 0, 0, 0, 0, 0, }, {0, 6, 2, 4, 4, 4, 4, 4, }}, { 70, 3, {1, 2, 6, 0, 0, 0, 0, 0, }, {1, 6, 2, 4, 4, 4, 4, 4, }}, { 71, 4, {0, 1, 2, 6, 0, 0, 0, 0, }, {0, 1, 6, 2, 4, 4, 4, 4, }}, { 72, 2, {3, 6, 0, 0, 0, 0, 0, 0, }, {6, 3, 4, 4, 4, 4, 4, 4, }}, { 73, 3, {0, 3, 6, 0, 0, 0, 0, 0, }, {4, 7, 2, 4, 4, 4, 4, 4, }}, { 74, 3, {1, 3, 6, 0, 0, 0, 0, 0, }, {3, 1, 6, 4, 4, 4, 4, 4, }}, { 75, 4, {0, 1, 3, 6, 0, 0, 0, 0, }, {0, 6, 3, 1, 4, 4, 4, 4, }}, { 76, 3, {2, 3, 6, 0, 0, 0, 0, 0, }, {6, 3, 2, 4, 4, 4, 4, 4, }}, { 77, 4, {0, 2, 3, 6, 0, 0, 0, 0, }, {0, 6, 3, 2, 4, 4, 4, 4, }}, { 78, 4, {1, 2, 3, 6, 0, 0, 0, 0, }, {1, 6, 3, 2, 4, 4, 4, 4, }}, { 79, 5, {0, 1, 2, 3, 6, 0, 0, 0, }, {0, 1, 6, 3, 2, 4, 4, 4, }}, { 80, 2, {4, 6, 0, 0, 0, 0, 0, 0, }, {6, 4, 4, 4, 4, 4, 4, 4, }}, { 81, 3, {0, 4, 6, 0, 0, 0, 0, 0, }, {4, 0, 6, 4, 4, 4, 4, 4, }}, { 82, 3, {1, 4, 6, 0, 0, 0, 0, 0, }, {5, 0, 2, 4, 4, 4, 4, 4, }}, { 83, 4, {0, 1, 4, 6, 0, 0, 0, 0, }, {4, 1, 0, 6, 4, 4, 4, 4, }}, { 84, 3, {2, 4, 6, 0, 0, 0, 0, 0, }, {6, 4, 2, 4, 4, 4, 4, 4, }}, { 85, 4, {0, 2, 4, 6, 0, 0, 0, 0, }, {4, 6, 0, 2, 4, 4, 4, 4, }}, { 86, 4, {1, 2, 4, 6, 0, 0, 0, 0, }, {1, 6, 4, 2, 4, 4, 4, 4, }}, { 87, 5, {0, 1, 2, 4, 6, 0, 0, 0, }, {4, 1, 6, 0, 2, 4, 4, 4, }}, { 88, 3, {3, 4, 6, 0, 0, 0, 0, 0, }, {6, 4, 3, 4, 4, 4, 4, 4, }}, { 89, 4, {0, 3, 4, 6, 0, 0, 0, 0, }, {4, 3, 0, 6, 4, 4, 4, 4, }}, { 90, 4, {1, 3, 4, 6, 0, 0, 0, 0, }, {1, 6, 4, 3, 4, 4, 4, 4, }}, { 91, 5, {0, 1, 3, 4, 6, 0, 0, 0, }, {4, 1, 3, 0, 6, 4, 4, 4, }}, { 92, 4, {2, 3, 4, 6, 0, 0, 0, 0, }, {6, 3, 4, 2, 4, 4, 4, 4, }}, { 93, 5, {0, 2, 3, 4, 6, 0, 0, 0, }, {4, 6, 3, 0, 2, 4, 4, 4, }}, { 94, 5, {1, 2, 3, 4, 6, 0, 0, 0, }, {1, 6, 3, 4, 2, 4, 4, 4, }}, { 95, 6, {0, 1, 2, 3, 4, 6, 0, 0, }, {4, 1, 6, 3, 0, 2, 4, 4, }}, { 96, 2, {5, 6, 0, 0, 0, 0, 0, 0, }, {6, 5, 4, 4, 4, 4, 4, 4, }}, { 97, 3, {0, 5, 6, 0, 0, 0, 0, 0, }, {5, 0, 6, 4, 4, 4, 4, 4, }}, { 98, 3, {1, 5, 6, 0, 0, 0, 0, 0, }, {5, 1, 6, 4, 4, 4, 4, 4, }}, { 99, 4, {0, 1, 5, 6, 0, 0, 0, 0, }, {0, 5, 1, 6, 4, 4, 4, 4, }}, {100, 3, {2, 5, 6, 0, 0, 0, 0, 0, }, {6, 5, 2, 4, 4, 4, 4, 4, }}, {101, 4, {0, 2, 5, 6, 0, 0, 0, 0, }, {0, 6, 5, 2, 4, 4, 4, 4, }}, {102, 4, {1, 2, 5, 6, 0, 0, 0, 0, }, {5, 6, 1, 2, 4, 4, 4, 4, }}, {103, 5, {0, 1, 2, 5, 6, 0, 0, 0, }, {0, 5, 6, 1, 2, 4, 4, 4, }}, {104, 3, {3, 5, 6, 0, 0, 0, 0, 0, }, {6, 5, 3, 4, 4, 4, 4, 4, }}, {105, 4, {0, 3, 5, 6, 0, 0, 0, 0, }, {5, 3, 0, 6, 4, 4, 4, 4, }}, {106, 4, {1, 3, 5, 6, 0, 0, 0, 0, }, {5, 6, 1, 3, 4, 4, 4, 4, }}, {107, 5, {0, 1, 3, 5, 6, 0, 0, 0, }, {0, 5, 3, 1, 6, 4, 4, 4, }}, {108, 4, {2, 3, 5, 6, 0, 0, 0, 0, }, {6, 3, 5, 2, 4, 4, 4, 4, }}, {109, 5, {0, 2, 3, 5, 6, 0, 0, 0, }, {0, 6, 3, 5, 2, 4, 4, 4, }}, {110, 5, {1, 2, 3, 5, 6, 0, 0, 0, }, {5, 6, 3, 1, 2, 4, 4, 4, }}, {111, 6, {0, 1, 2, 3, 5, 6, 0, 0, }, {0, 5, 6, 3, 1, 2, 4, 4, }}, {112, 3, {4, 5, 6, 0, 0, 0, 0, 0, }, {6, 5, 4, 4, 4, 4, 4, 4, }}, {113, 4, {0, 4, 5, 6, 0, 0, 0, 0, }, {4, 0, 5, 6, 4, 4, 4, 4, }}, {114, 4, {1, 4, 5, 6, 0, 0, 0, 0, }, {5, 4, 1, 6, 4, 4, 4, 4, }}, {115, 5, {0, 1, 4, 5, 6, 0, 0, 0, }, {4, 5, 0, 1, 6, 4, 4, 4, }}, {116, 4, {2, 4, 5, 6, 0, 0, 0, 0, }, {6, 4, 5, 2, 4, 4, 4, 4, }}, {117, 5, {0, 2, 4, 5, 6, 0, 0, 0, }, {4, 6, 0, 5, 2, 4, 4, 4, }}, {118, 5, {1, 2, 4, 5, 6, 0, 0, 0, }, {5, 6, 4, 1, 2, 4, 4, 4, }}, {119, 6, {0, 1, 2, 4, 5, 6, 0, 0, }, {4, 5, 6, 0, 1, 2, 4, 4, }}, {120, 4, {3, 4, 5, 6, 0, 0, 0, 0, }, {6, 4, 5, 3, 4, 4, 4, 4, }}, {121, 5, {0, 3, 4, 5, 6, 0, 0, 0, }, {4, 3, 0, 5, 6, 4, 4, 4, }}, {122, 5, {1, 3, 4, 5, 6, 0, 0, 0, }, {5, 3, 4, 1, 6, 4, 4, 4, }}, {123, 6, {0, 1, 3, 4, 5, 6, 0, 0, }, {4, 5, 3, 0, 1, 6, 4, 4, }}, {124, 5, {2, 3, 4, 5, 6, 0, 0, 0, }, {6, 3, 4, 5, 2, 4, 4, 4, }}, {125, 6, {0, 2, 3, 4, 5, 6, 0, 0, }, {4, 6, 3, 0, 5, 2, 4, 4, }}, {126, 6, {1, 2, 3, 4, 5, 6, 0, 0, }, {5, 6, 3, 4, 1, 2, 4, 4, }}, {127, 7, {0, 1, 2, 3, 4, 5, 6, 0, }, {4, 5, 6, 3, 0, 1, 2, 4, }}, {128, 1, {7, 0, 0, 0, 0, 0, 0, 0, }, {7, 4, 4, 4, 4, 4, 4, 4, }}, {129, 2, {0, 7, 0, 0, 0, 0, 0, 0, }, {7, 0, 4, 4, 4, 4, 4, 4, }}, {130, 2, {1, 7, 0, 0, 0, 0, 0, 0, }, {7, 1, 4, 4, 4, 4, 4, 4, }}, {131, 3, {0, 1, 7, 0, 0, 0, 0, 0, }, {0, 7, 1, 4, 4, 4, 4, 4, }}, {132, 2, {2, 7, 0, 0, 0, 0, 0, 0, }, {7, 2, 4, 4, 4, 4, 4, 4, }}, {133, 3, {0, 2, 7, 0, 0, 0, 0, 0, }, {0, 7, 2, 4, 4, 4, 4, 4, }}, {134, 3, {1, 2, 7, 0, 0, 0, 0, 0, }, {1, 7, 2, 4, 4, 4, 4, 4, }}, {135, 4, {0, 1, 2, 7, 0, 0, 0, 0, }, {0, 1, 7, 2, 4, 4, 4, 4, }}, {136, 2, {3, 7, 0, 0, 0, 0, 0, 0, }, {7, 3, 4, 4, 4, 4, 4, 4, }}, {137, 3, {0, 3, 7, 0, 0, 0, 0, 0, }, {0, 7, 3, 4, 4, 4, 4, 4, }}, {138, 3, {1, 3, 7, 0, 0, 0, 0, 0, }, {1, 7, 3, 4, 4, 4, 4, 4, }}, {139, 4, {0, 1, 3, 7, 0, 0, 0, 0, }, {0, 1, 7, 3, 4, 4, 4, 4, }}, {140, 3, {2, 3, 7, 0, 0, 0, 0, 0, }, {2, 7, 3, 4, 4, 4, 4, 4, }}, {141, 4, {0, 2, 3, 7, 0, 0, 0, 0, }, {0, 2, 7, 3, 4, 4, 4, 4, }}, {142, 4, {1, 2, 3, 7, 0, 0, 0, 0, }, {1, 2, 7, 3, 4, 4, 4, 4, }}, {143, 5, {0, 1, 2, 3, 7, 0, 0, 0, }, {0, 1, 2, 7, 3, 4, 4, 4, }}, {144, 2, {4, 7, 0, 0, 0, 0, 0, 0, }, {7, 4, 4, 4, 4, 4, 4, 4, }}, {145, 3, {0, 4, 7, 0, 0, 0, 0, 0, }, {4, 0, 7, 4, 4, 4, 4, 4, }}, {146, 3, {1, 4, 7, 0, 0, 0, 0, 0, }, {7, 4, 1, 4, 4, 4, 4, 4, }}, {147, 4, {0, 1, 4, 7, 0, 0, 0, 0, }, {4, 1, 0, 7, 4, 4, 4, 4, }}, {148, 3, {2, 4, 7, 0, 0, 0, 0, 0, }, {6, 0, 3, 4, 4, 4, 4, 4, }}, {149, 4, {0, 2, 4, 7, 0, 0, 0, 0, }, {4, 2, 0, 7, 4, 4, 4, 4, }}, {150, 4, {1, 2, 4, 7, 0, 0, 0, 0, }, {4, 2, 1, 7, 4, 4, 4, 4, }}, {151, 5, {0, 1, 2, 4, 7, 0, 0, 0, }, {4, 1, 2, 0, 7, 4, 4, 4, }}, {152, 3, {3, 4, 7, 0, 0, 0, 0, 0, }, {7, 4, 3, 4, 4, 4, 4, 4, }}, {153, 4, {0, 3, 4, 7, 0, 0, 0, 0, }, {4, 7, 0, 3, 4, 4, 4, 4, }}, {154, 4, {1, 3, 4, 7, 0, 0, 0, 0, }, {4, 7, 1, 3, 4, 4, 4, 4, }}, {155, 5, {0, 1, 3, 4, 7, 0, 0, 0, }, {4, 1, 7, 0, 3, 4, 4, 4, }}, {156, 4, {2, 3, 4, 7, 0, 0, 0, 0, }, {2, 7, 4, 3, 4, 4, 4, 4, }}, {157, 5, {0, 2, 3, 4, 7, 0, 0, 0, }, {4, 2, 7, 0, 3, 4, 4, 4, }}, {158, 5, {1, 2, 3, 4, 7, 0, 0, 0, }, {1, 2, 7, 4, 3, 4, 4, 4, }}, {159, 6, {0, 1, 2, 3, 4, 7, 0, 0, }, {4, 1, 2, 7, 0, 3, 4, 4, }}, {160, 2, {5, 7, 0, 0, 0, 0, 0, 0, }, {7, 5, 4, 4, 4, 4, 4, 4, }}, {161, 3, {0, 5, 7, 0, 0, 0, 0, 0, }, {5, 0, 7, 4, 4, 4, 4, 4, }}, {162, 3, {1, 5, 7, 0, 0, 0, 0, 0, }, {5, 1, 7, 4, 4, 4, 4, 4, }}, {163, 4, {0, 1, 5, 7, 0, 0, 0, 0, }, {0, 5, 1, 7, 4, 4, 4, 4, }}, {164, 3, {2, 5, 7, 0, 0, 0, 0, 0, }, {2, 7, 5, 4, 4, 4, 4, 4, }}, {165, 4, {0, 2, 5, 7, 0, 0, 0, 0, }, {0, 7, 5, 2, 4, 4, 4, 4, }}, {166, 4, {1, 2, 5, 7, 0, 0, 0, 0, }, {5, 7, 1, 2, 4, 4, 4, 4, }}, {167, 5, {0, 1, 2, 5, 7, 0, 0, 0, }, {0, 5, 2, 1, 7, 4, 4, 4, }}, {168, 3, {3, 5, 7, 0, 0, 0, 0, 0, }, {7, 5, 3, 4, 4, 4, 4, 4, }}, {169, 4, {0, 3, 5, 7, 0, 0, 0, 0, }, {5, 7, 0, 3, 4, 4, 4, 4, }}, {170, 4, {1, 3, 5, 7, 0, 0, 0, 0, }, {5, 7, 1, 3, 4, 4, 4, 4, }}, {171, 5, {0, 1, 3, 5, 7, 0, 0, 0, }, {0, 5, 7, 1, 3, 4, 4, 4, }}, {172, 4, {2, 3, 5, 7, 0, 0, 0, 0, }, {5, 7, 2, 3, 4, 4, 4, 4, }}, {173, 5, {0, 2, 3, 5, 7, 0, 0, 0, }, {0, 2, 7, 5, 3, 4, 4, 4, }}, {174, 5, {1, 2, 3, 5, 7, 0, 0, 0, }, {5, 2, 7, 1, 3, 4, 4, 4, }}, {175, 6, {0, 1, 2, 3, 5, 7, 0, 0, }, {0, 5, 2, 7, 1, 3, 4, 4, }}, {176, 3, {4, 5, 7, 0, 0, 0, 0, 0, }, {7, 5, 4, 4, 4, 4, 4, 4, }}, {177, 4, {0, 4, 5, 7, 0, 0, 0, 0, }, {4, 0, 5, 7, 4, 4, 4, 4, }}, {178, 4, {1, 4, 5, 7, 0, 0, 0, 0, }, {5, 7, 1, 4, 4, 4, 4, 4, }}, {179, 5, {0, 1, 4, 5, 7, 0, 0, 0, }, {4, 5, 0, 1, 7, 4, 4, 4, }}, {180, 4, {2, 4, 5, 7, 0, 0, 0, 0, }, {5, 4, 2, 7, 4, 4, 4, 4, }}, {181, 5, {0, 2, 4, 5, 7, 0, 0, 0, }, {4, 2, 0, 5, 7, 4, 4, 4, }}, {182, 5, {1, 2, 4, 5, 7, 0, 0, 0, }, {5, 2, 4, 1, 7, 4, 4, 4, }}, {183, 6, {0, 1, 2, 4, 5, 7, 0, 0, }, {4, 5, 2, 0, 1, 7, 4, 4, }}, {184, 4, {3, 4, 5, 7, 0, 0, 0, 0, }, {7, 4, 5, 3, 4, 4, 4, 4, }}, {185, 5, {0, 3, 4, 5, 7, 0, 0, 0, }, {4, 7, 0, 5, 3, 4, 4, 4, }}, {186, 5, {1, 3, 4, 5, 7, 0, 0, 0, }, {5, 7, 4, 1, 3, 4, 4, 4, }}, {187, 6, {0, 1, 3, 4, 5, 7, 0, 0, }, {4, 5, 7, 0, 1, 3, 4, 4, }}, {188, 5, {2, 3, 4, 5, 7, 0, 0, 0, }, {2, 7, 4, 5, 3, 4, 4, 4, }}, {189, 6, {0, 2, 3, 4, 5, 7, 0, 0, }, {4, 2, 7, 0, 5, 3, 4, 4, }}, {190, 6, {1, 2, 3, 4, 5, 7, 0, 0, }, {5, 2, 7, 4, 1, 3, 4, 4, }}, {191, 7, {0, 1, 2, 3, 4, 5, 7, 0, }, {4, 5, 2, 7, 0, 1, 3, 4, }}, {192, 2, {6, 7, 0, 0, 0, 0, 0, 0, }, {7, 6, 4, 4, 4, 4, 4, 4, }}, {193, 3, {0, 6, 7, 0, 0, 0, 0, 0, }, {6, 0, 7, 4, 4, 4, 4, 4, }}, {194, 3, {1, 6, 7, 0, 0, 0, 0, 0, }, {6, 1, 7, 4, 4, 4, 4, 4, }}, {195, 4, {0, 1, 6, 7, 0, 0, 0, 0, }, {0, 6, 1, 7, 4, 4, 4, 4, }}, {196, 3, {2, 6, 7, 0, 0, 0, 0, 0, }, {6, 2, 7, 4, 4, 4, 4, 4, }}, {197, 4, {0, 2, 6, 7, 0, 0, 0, 0, }, {0, 6, 2, 7, 4, 4, 4, 4, }}, {198, 4, {1, 2, 6, 7, 0, 0, 0, 0, }, {1, 6, 2, 7, 4, 4, 4, 4, }}, {199, 5, {0, 1, 2, 6, 7, 0, 0, 0, }, {0, 1, 6, 2, 7, 4, 4, 4, }}, {200, 3, {3, 6, 7, 0, 0, 0, 0, 0, }, {7, 6, 3, 4, 4, 4, 4, 4, }}, {201, 4, {0, 3, 6, 7, 0, 0, 0, 0, }, {0, 7, 6, 3, 4, 4, 4, 4, }}, {202, 4, {1, 3, 6, 7, 0, 0, 0, 0, }, {6, 7, 1, 3, 4, 4, 4, 4, }}, {203, 5, {0, 1, 3, 6, 7, 0, 0, 0, }, {0, 1, 7, 6, 3, 4, 4, 4, }}, {204, 4, {2, 3, 6, 7, 0, 0, 0, 0, }, {6, 7, 2, 3, 4, 4, 4, 4, }}, {205, 5, {0, 2, 3, 6, 7, 0, 0, 0, }, {0, 6, 7, 2, 3, 4, 4, 4, }}, {206, 5, {1, 2, 3, 6, 7, 0, 0, 0, }, {1, 6, 7, 2, 3, 4, 4, 4, }}, {207, 6, {0, 1, 2, 3, 6, 7, 0, 0, }, {0, 1, 6, 7, 2, 3, 4, 4, }}, {208, 3, {4, 6, 7, 0, 0, 0, 0, 0, }, {7, 6, 4, 4, 4, 4, 4, 4, }}, {209, 4, {0, 4, 6, 7, 0, 0, 0, 0, }, {4, 0, 6, 7, 4, 4, 4, 4, }}, {210, 4, {1, 4, 6, 7, 0, 0, 0, 0, }, {1, 7, 6, 4, 4, 4, 4, 4, }}, {211, 5, {0, 1, 4, 6, 7, 0, 0, 0, }, {4, 1, 0, 6, 7, 4, 4, 4, }}, {212, 4, {2, 4, 6, 7, 0, 0, 0, 0, }, {6, 4, 2, 7, 4, 4, 4, 4, }}, {213, 5, {0, 2, 4, 6, 7, 0, 0, 0, }, {4, 6, 0, 2, 7, 4, 4, 4, }}, {214, 5, {1, 2, 4, 6, 7, 0, 0, 0, }, {1, 6, 4, 2, 7, 4, 4, 4, }}, {215, 6, {0, 1, 2, 4, 6, 7, 0, 0, }, {4, 1, 6, 0, 2, 7, 4, 4, }}, {216, 4, {3, 4, 6, 7, 0, 0, 0, 0, }, {7, 4, 6, 3, 4, 4, 4, 4, }}, {217, 5, {0, 3, 4, 6, 7, 0, 0, 0, }, {4, 7, 0, 6, 3, 4, 4, 4, }}, {218, 5, {1, 3, 4, 6, 7, 0, 0, 0, }, {1, 7, 4, 6, 3, 4, 4, 4, }}, {219, 6, {0, 1, 3, 4, 6, 7, 0, 0, }, {4, 1, 7, 0, 6, 3, 4, 4, }}, {220, 5, {2, 3, 4, 6, 7, 0, 0, 0, }, {6, 7, 4, 2, 3, 4, 4, 4, }}, {221, 6, {0, 2, 3, 4, 6, 7, 0, 0, }, {4, 6, 7, 0, 2, 3, 4, 4, }}, {222, 6, {1, 2, 3, 4, 6, 7, 0, 0, }, {1, 6, 7, 4, 2, 3, 4, 4, }}, {223, 7, {0, 1, 2, 3, 4, 6, 7, 0, }, {4, 1, 6, 7, 0, 2, 3, 4, }}, {224, 3, {5, 6, 7, 0, 0, 0, 0, 0, }, {7, 6, 5, 4, 4, 4, 4, 4, }}, {225, 4, {0, 5, 6, 7, 0, 0, 0, 0, }, {5, 0, 6, 7, 4, 4, 4, 4, }}, {226, 4, {1, 5, 6, 7, 0, 0, 0, 0, }, {5, 1, 6, 7, 4, 4, 4, 4, }}, {227, 5, {0, 1, 5, 6, 7, 0, 0, 0, }, {0, 5, 1, 6, 7, 4, 4, 4, }}, {228, 4, {2, 5, 6, 7, 0, 0, 0, 0, }, {6, 5, 2, 7, 4, 4, 4, 4, }}, {229, 5, {0, 2, 5, 6, 7, 0, 0, 0, }, {0, 6, 5, 2, 7, 4, 4, 4, }}, {230, 5, {1, 2, 5, 6, 7, 0, 0, 0, }, {5, 6, 1, 2, 7, 4, 4, 4, }}, {231, 6, {0, 1, 2, 5, 6, 7, 0, 0, }, {0, 5, 6, 1, 2, 7, 4, 4, }}, {232, 4, {3, 5, 6, 7, 0, 0, 0, 0, }, {7, 5, 6, 3, 4, 4, 4, 4, }}, {233, 5, {0, 3, 5, 6, 7, 0, 0, 0, }, {0, 7, 5, 6, 3, 4, 4, 4, }}, {234, 5, {1, 3, 5, 6, 7, 0, 0, 0, }, {5, 7, 1, 6, 3, 4, 4, 4, }}, {235, 6, {0, 1, 3, 5, 6, 7, 0, 0, }, {0, 5, 7, 1, 6, 3, 4, 4, }}, {236, 5, {2, 3, 5, 6, 7, 0, 0, 0, }, {6, 7, 5, 2, 3, 4, 4, 4, }}, {237, 6, {0, 2, 3, 5, 6, 7, 0, 0, }, {0, 6, 7, 5, 2, 3, 4, 4, }}, {238, 6, {1, 2, 3, 5, 6, 7, 0, 0, }, {5, 6, 7, 1, 2, 3, 4, 4, }}, {239, 7, {0, 1, 2, 3, 5, 6, 7, 0, }, {0, 5, 6, 7, 1, 2, 3, 4, }}, {240, 4, {4, 5, 6, 7, 0, 0, 0, 0, }, {7, 5, 6, 4, 4, 4, 4, 4, }}, {241, 5, {0, 4, 5, 6, 7, 0, 0, 0, }, {4, 0, 5, 6, 7, 4, 4, 4, }}, {242, 5, {1, 4, 5, 6, 7, 0, 0, 0, }, {5, 4, 1, 6, 7, 4, 4, 4, }}, {243, 6, {0, 1, 4, 5, 6, 7, 0, 0, }, {4, 5, 0, 1, 6, 7, 4, 4, }}, {244, 5, {2, 4, 5, 6, 7, 0, 0, 0, }, {6, 4, 5, 2, 7, 4, 4, 4, }}, {245, 6, {0, 2, 4, 5, 6, 7, 0, 0, }, {4, 6, 0, 5, 2, 7, 4, 4, }}, {246, 6, {1, 2, 4, 5, 6, 7, 0, 0, }, {5, 6, 4, 1, 2, 7, 4, 4, }}, {247, 7, {0, 1, 2, 4, 5, 6, 7, 0, }, {4, 5, 6, 0, 1, 2, 7, 4, }}, {248, 5, {3, 4, 5, 6, 7, 0, 0, 0, }, {7, 4, 5, 6, 3, 4, 4, 4, }}, {249, 6, {0, 3, 4, 5, 6, 7, 0, 0, }, {4, 7, 0, 5, 6, 3, 4, 4, }}, {250, 6, {1, 3, 4, 5, 6, 7, 0, 0, }, {5, 7, 4, 1, 6, 3, 4, 4, }}, {251, 7, {0, 1, 3, 4, 5, 6, 7, 0, }, {4, 5, 7, 0, 1, 6, 3, 4, }}, {252, 6, {2, 3, 4, 5, 6, 7, 0, 0, }, {6, 7, 4, 5, 2, 3, 4, 4, }}, {253, 7, {0, 2, 3, 4, 5, 6, 7, 0, }, {4, 6, 7, 0, 5, 2, 3, 4, }}, {254, 7, {1, 2, 3, 4, 5, 6, 7, 0, }, {5, 6, 7, 4, 1, 2, 3, 4, }}, {255, 8, {0, 1, 2, 3, 4, 5, 6, 7, }, {4, 5, 6, 7, 0, 1, 2, 3, }}, }; #define BS 192 #define BSS 160 #define BSC 224 //時刻 t から時刻 t-1 にさかのぼる __device__ char crashFD[1]; void *crashFD_p; __global__ void step_back(int t){ int i, j; char crash_n = 0; //時刻 t-1 のときに (x,y) で衝突していた粒子の個数 int pat = 0; //相対位置 k の粒子が時刻 t-1 で(x,y)にいたとき k 番目のビットが 1 になる int x, y, adx, ady; int line = blockIdx.x * blockDim.x + threadIdx.x; x = line / MAXN; y = line - x * MAXN; if(x >= MAXN || y >= MAXN) return; //各隣接格子点に対して for(i = 0; i < 8; i++){ adx = adjxD[x][i]; ady = adjyD[y][i]; //隣接したマスに時刻 t-1 のとき(x,y)だった粒子が存在しないかみる for(j = 0; j < univ_nD[IDXN3(t,adx,ady,MAXN)]; j++){ //粒子を発見したとき if(i == univ_vD[IDXN4(t,adx,ady,j,MAXN)]){ pat = BIT(pat,i); univ_cD[IDXN4(t+1,x,y,crash_n,MAXN)] univ_cD[IDXN4(t,adx,ady,j,MAXN)]; crash_n++; break; } } } univ_nD[IDXN3(t+1,x,y,MAXN)] = crash_n; //crash_v を変換して univ_v[t-1][x][y] に代入していく処理↓ for(i = 0; i < crash_n; i++){ univ_vD[IDXN4(t+1,x,y,i,MAXN)] = new_transition_rulesD[pat].next[i]; } //2 つ以上の粒子が衝突したとき if(2 <= crash_n){ crashFD[0] = 1; } } __device__ char sameD[1]; void *sameD_p; __global__ void check_sub(int t, int k){ int x, y; int line = blockIdx.x * blockDim.x + threadIdx.x; x = line / MAXN; y = line - x * MAXN; if(x >= MAXN || y >= MAXN) return; if(univ_nD[IDXN3(t,x,y,MAXN)] == 1 && (univA_vD[IDXN_UA(k,x,y,MAXN)] != univ_vD[IDXN4(t,x,y,0,MAXN)] || univA_cD[IDXN_UA(k,x,y,MAXN)] != univ_cD[IDXN4(t,x,y,0,MAXN)])){ sameD[0] = 1; } } int check(int t, int k){ char same = 0; cudaMemcpy(sameD_p, &same, sizeof(char), cudaMemcpyHostToDevice); check_sub<<<(N*N+BSC-1)/BSC, BSC>>>(t, k); cudaMemcpy(&same, sameD_p, sizeof(char), cudaMemcpyDeviceToHost); return same; } __global__ void initB(int univ){ int i = blockIdx.x * blockDim.x + threadIdx.x; if(i >= 3 * MAXM) return; int x, y; x = BD[univ][i].x; y = BD[univ][i].y; univ_vD[IDXN4(0,x,y,0,MAXN)] = (char)BD[univ][i].dir; univ_cD[IDXN4(0,x,y,0,MAXN)] = (char)BD[univ][i].color; univ_nD[IDXN3(0,x,y,MAXN)] = 1; } /********* 各自のプログラムはここまで **********/ /********* テンプレート用 (2) ここから再開 **********/ int main() { struct timeval tstart, tlast; input(); gettimeofday(&tstart, NULL); printf("[TEMPLATE] ...end of input...\n"); fflush(stdout); /********* テンプレート用 (2) ここまで **********/ /********* 以下に各自のプログラムを書く **********/ { int i, k, t; int univ; char a_det[MAXK]; void *univ_n_p; void *univA_v_p; void *univA_c_p; //init cudaDeviceSynchronize(); cudaDeviceSetCacheConfig(cudaFuncCachePreferL1); memset(a_det, 0, sizeof(char) * K); cudaGetSymbolAddress(&sameD_p, sameD); cudaGetSymbolAddress(&crashFD_p, crashFD); cudaGetSymbolAddress(&univ_n_p, univ_nD); cudaGetSymbolAddress(&univA_v_p, univA_vD); cudaGetSymbolAddress(&univA_c_p, univA_cD); cudaGetSymbolAddress(&BD_p, BD); cudaGetSymbolAddress(&adjxD_p, adjxD); cudaGetSymbolAddress(&adjyD_p, adjyD); cudaMemcpy(BD_p, B, sizeof(Star) * MAXL * 3 * MAXM, cudaMemcpyHostToDevice); //隣接点を事前に計算しておく for(i = 0; i < MAXN; i++){ for(k = 0; k < 8; k++){ int adx = i + dx[k]; int ady = i + dy[k]; if(adx == MAXN) adx = 0; if(adx == -1) adx = MAXN - 1; if(ady == MAXN) ady = 0; if(ady == -1) ady = MAXN - 1; adjx[i][k] = adx; adjy[i][k] = ady; } } cudaMemcpy(adjxD_p, adjx, sizeof(int) * MAXN * 8, cudaMemcpyHostToDevice); cudaMemcpy(adjyD_p, adjy, sizeof(int) * MAXN * 8, cudaMemcpyHostToDevice); //宇宙 A のコピー for(univ = 0; univ < K; univ++){ for(i = 0; i < 3 * M; i++){ int x, y, dir, col; x = A[univ][i].x; y = A[univ][i].y; dir = (char)A[univ][i].dir; col = (char)A[univ][i].color; univA_v[IDXN_UA(univ,x,y,MAXN)] = dir; univA_c[IDXN_UA(univ,x,y,MAXN)] = col; } } cudaMemcpy(univA_v_p, univA_v, sizeof(char) * MAXK * MAXN * MAXN, univA_c, sizeof(char) * MAXK * MAXN * MAXN, cudaMemcpyHostToDevice); cudaMemcpy(univA_c_p, cudaMemcpyHostToDevice); for(univ = 0; univ < L; univ++){ //宇宙 B をひとつずつみていく memset(univ_n, 0, sizeof(char) * MAXN * MAXN); cudaMemcpy(univ_n_p, univ_n, sizeof(char)*MAXN*MAXN, cudaMemcpyHostToDevice); initB<<<(3*M+BS-1)/BS, BS>>>(univ); for(t = 0; t < T * 2; t++){ int crashF = 0; if(t + 1 > T / 2) cudaMemcpy(crashFD_p, &crashF, sizeof(char),sizeof(char), cudaMemcpyHostToDevice); step_back<<<(N*N+BSS-1)/BSS, BSS>>>(t); if(t + 1 > T / 2) cudaMemcpy(&crashF, crashFD_p, sizeof(char), cudaMemcpyDeviceToHost); if(t + 1 > T / 2 && crashF == 0){ for(i = 0; i < K; i++){ if(a_det[i] == 1) continue; if(check(t+1, i) == 0){ //等しいならば 0 異なれば 1 answer[univ] = i; a_det[i] = 1; goto end; } } } } end: ; } } /********* 各自のプログラムはここまで **********/ /********* テンプレート用 (3) ここから再開，最後まで **********/ gettimeofday(&tlast, NULL); fflush(stdout); printf("[TEMPLATE] time %lf seconds\n", (double)(tlast.tv_sec - tstart.tv_sec)+ (double)(tlast.tv_usec - tstart.tv_usec)/ 1000000); output(); printf("[TEMPLATE] end of execution\n"); return 0; }
