結果

問題 No.3 ビットすごろく
コンテスト
ユーザー kapo
提出日時 2016-04-24 12:39:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 2,608 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 331 ms
コンパイル使用メモリ 26,620 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-04 15:36:08
合計ジャッジ時間 10,126 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 2 RE * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:26:22: warning: NULL used in arithmetic [-Wpointer-arith]
   26 |         if(ans[1] != NULL) {
      |                      ^~~~
main.cpp: In function ‘int search(int, int)’:
main.cpp:52:63: warning: NULL used in arithmetic [-Wpointer-arith]
   52 |                                                 if( ans[1] == NULL || ans[1] >len) {
      |                                                               ^~~~
main.cpp: In function ‘int b_search(int*, int, int)’:
main.cpp:119:16: warning: converting to non-pointer type ‘int’ from NULL [-Wconversion-null]
  119 |         return NULL;
      |                ^~~~
main.cpp: In function ‘int main()’:
main.cpp:23:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   23 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NODE 1000
#define SIZE 1000

/* Queue */
int path[SIZE][NODE];
int length[SIZE];
int root[NODE];
int ans[2];

int bitCount( int bit);
int search( int start, int goal);
int b_search( int *array, int target, int size);
void quick_sort( int *array, int left, int right);
void change(int &a, int &b);

int main(void)
{
	int n, i;
	scanf("%d", &n);
	search(1, n);

	if(ans[1] != NULL) {
		printf("%d\n", ans[1]+2);
	} else {
		printf("-1");
	}
	return 0;
}

int search(int start, int goal)
{
	int rear = 1, front = 0, root_cnt = 1;
	path[0][0] = start;
	length[0] = 0;
	root[0] = start;

	while( front < rear ) {
		int len = length[front];
		int node = path[front][len];
		int i, bit = bitCount(path[front][len]);

		for( i = 0; i < 2; i++) {
			quick_sort(root, 0, root_cnt-1);
			switch(i) {
			case 0:
				if( b_search(root, path[front][len]+bit, root_cnt) != 1) {
					if( path[front][len]+bit == goal ) {
						if( ans[1] == NULL || ans[1] >len) {
							ans[0] = front;
							ans[1] = len;
						}
					} else if( path[front][len]+bit < goal) {
						root[root_cnt] = path[front][len]+bit;
						root_cnt++;
						int j;
						for( j = 0; j <= len; j++) {
							path[rear][j] = path[front][j];
						}
						path[rear][len+1] = path[front][len]+bit;
						length[rear] = len + 1;
						rear++;
					}
				}
				break;
			case 1:
				if( b_search(root, path[front][len]-bit, root_cnt) != 1
				&& path[front][len] < goal
				&& path[front][len]-bit > 0) {
					root[root_cnt] = path[front][len]-bit;
					root_cnt++;
					int j;
					for( j = 0; j <= len; j++) {
						path[rear][j] = path[front][j];
					}
					path[rear][len+1] = path[front][len]-bit;
					length[rear] = len + 1;
					rear++;
				}
				break;
			}
		}
		front++;
	}


	return 0;
}


int bitCount(int bit)
{
	int cnt = 0;
	for( ; bit != 0; bit>>=1) {
		cnt += bit & 1;
	}

	return cnt;
}

int b_search( int *array, int target, int size)
{
	int min = 0, max = size-1, mid;

	while( min <= max) {
		mid = (min+max)/2;

		if( array[mid] == target) {
			return 1;
		} else if( array[mid] < target) {
			min = mid+1;
		} else if ( array[mid] > target) {
			max = mid-1;
		}
	}
	return NULL;
}

void quick_sort(int *array, int left, int right)
{
	if( left >= right) return;

	int p = left, k = p+1;

	while( k <= right ) {
		if( array[k] < array[left] ) {
			change(array[k], array[p+1]);
			p++;
		}
		k++;
	}
	change(array[left], array[p]);
	quick_sort(array, left, p-1);
	quick_sort(array, p+1, right);
}

void change(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
0