アルゴリズム::白準::シミュレーション::15662::歯車(2)

質問する

質問へのアクセス

問題を理解する

コード#コード#

並べ方(大部分はこのように抱いている)

#include <cstdio>

int T, K;
bool gear[1001][8];	// N 0, S 1 

void roll(int num, bool dir) {
	if (dir) {	// clockwise
		bool tmp = gear[num][7];
		for (int i = 7; i > 0; --i)
			gear[num][i] = gear[num][i - 1];
		gear[num][0] = tmp;
	} else {	// counterclockwise
		bool tmp = gear[num][0];
		for (int i = 0; i < 7; ++i)
			gear[num][i] = gear[num][i + 1];
		gear[num][7] = tmp;
	}
}
void solve(int num, bool dir) {
	bool oldDir = dir;
	int left, right;
	for (left = num; left > 1; --left) // left side
		if (gear[left][6] == gear[left - 1][2]) break;
	for (right = num; right < T; ++right) // right side
		if (gear[right][2] == gear[right + 1][6]) break;
	
	roll(num, dir);
	dir = !dir;
	for (int i = num - 1; i >= left; --i) roll(i, dir), dir = !dir;
	dir = !oldDir;
	for (int i = num + 1; i <= right; ++i) roll(i, dir), dir = !dir;
}

int main() {
	int polar = 0, num = 0, dir = 0, ans = 0;
	// Step 1. Input gear information.
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i)
		for (int j = 0; j < 8; ++j)
			scanf("%1d", &polar), gear[i][j] = polar ? true : false;
	// Step 2. Roll gears.
	scanf("%d", &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d", &num, &dir);
		solve(num, dir == 1);
	}
	// Step 3. Count and print answer.
	for (int i = 1; i <= T; ++i)
		if (gear[i][0]) ans++;
	printf("%d\n", ans);
}

ビット演算方式

#include <cstdio>
int T, K, gear[1001];

void roll(int num, bool dir) {
	if (dir) {
		bool tmp = gear[num] & 1;
		gear[num] >>= 1;
		if (tmp) gear[num] |= (1 << 7);
	} else {
		bool tmp = gear[num] & (1 << 7);
		gear[num] <<= 1;
		if (tmp) gear[num] |= 1;
	}
}

void solve(int num, bool dir) {
	bool oldDir = dir;
	int left = num, right = num;
	for (; left > 1; --left) {
		bool lhs = gear[left] & (1 << 1);
		bool rhs = gear[left - 1] & (1 << 5);
		if (lhs == rhs) break;
	}
	for (; right < T; ++right) {
		bool lhs = gear[right] & (1 << 5);
		bool rhs = gear[right + 1] & (1 << 1);
		if (lhs == rhs) break;
	}
	roll(num, dir);
	dir = !dir;
	for (int i = num - 1; i >= left; --i) roll(i, dir), dir = !dir;
	dir = !oldDir;
	for (int i = num + 1; i <= right; ++i) roll(i, dir), dir = !dir;
}

int main() {
	int polar = 0, num = 0, dir = 0, ans = 0;
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		for (int j = 7; j >= 0; --j) {
			scanf("%1d", &polar);
			if (polar) gear[i] |= (1 << j);
		}
	}
	scanf("%d", &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d", &num, &dir);
		solve(num, dir == 1);
	}
	for (int i = 1; i <= T; ++i)
		if (gear[i] & (1 << 7)) ans++;
	printf("%d\n", ans);
}

結果