QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113885#6644. Red Black GridITMO_pengzoo#AC ✓24ms9464kbC++2011.7kb2023-06-19 23:20:122023-06-19 23:20:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 23:20:13]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:9464kb
  • [2023-06-19 23:20:12]
  • 提交

answer

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
    if constexpr (index == std::tuple_size<T>::value) {
        out << ")";
        return out;
    } else {
        if (index > 0) {
            out << ", ";
        } else {
            out << "(";
        }
        out << std::get<index>(t);
        return print_tuple<index + 1, T>(out, t);
    }
}

template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
    return print_tuple<0, std::tuple<T...>>(out, t);
}

template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it) {
        if (it != container.begin()) {
            out << ", ";
        }
        out << *it;
    }
    out << "}";
    return out;
}

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 1100;

int color[N][N];
bool changed[N][N];

bool solve(int n, int k, int c) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			changed[i][j] = false;
		}
	}

	int cur = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i + 1 < n && color[i][j] != color[i + 1][j]) {
				++cur;
			}
			if (j + 1 < n && color[i][j] != color[i][j + 1]) {
				++cur;
			}
		}
	}
	assert(cur >= k);

	int cnt4 = 0, cnt3 = 0, cnt2 = 0;
	int free4 = 0, free3 = 0, free2 = 0;

	auto isSide = [&](int coord) {
		return coord == 0 || coord == n - 1;
	};	

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (color[i][j] != c) {
				continue;
			}

			if (isSide(i) && isSide(j)) {
				++free2;
			} else if (isSide(i) || isSide(j)) {
				++free3;
			} else {
				++free4;
			}
		}
	}

	int diff = cur - k;
	// debug(diff);
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < n - 1; ++j) {
			if (color[i][j] != c) {
				continue;
			}
			if (diff - 4 >= 0) {
				color[i][j] ^= 1;
				diff -= 4;
				++cnt4;
				changed[i][j] = true;
			}
		}
	}

	for (int i = 1; i < n - 1; ++i) {
		if (color[0][i] == c && diff - 3 >= 0) {
			color[0][i] ^= 1;
			diff -= 3;
			++cnt3;
			changed[0][i] = true;
		}
		if (color[n - 1][i] == c && diff - 3 >= 0) {
			color[n - 1][i] ^= 1;
			diff -= 3;
			++cnt3;
			changed[n - 1][i] = true;
		}
		if (color[i][0] == c && diff - 3 >= 0) {
			color[i][0] ^= 1;
			diff -= 3;
			++cnt3;
			changed[i][0] = true;
		}
		if (color[i][n - 1] == c && diff - 3 >= 0) {
			color[i][n - 1] ^= 1;
			diff -= 3;
			++cnt3;
			changed[i][n - 1] = true;
		}
	}

	if (color[0][0] == c && diff - 2 >= 0) {
		color[0][0] ^= 1;
		diff -= 2;
		++cnt2;
		changed[0][0] = true;
	}
	if (color[0][n - 1] == c && diff - 2 >= 0) {
		color[0][n - 1] ^= 1;
		diff -= 2;
		++cnt2;
		changed[0][n - 1] = true;
	}
	if (color[n - 1][0] == c && diff - 2 >= 0) {
		color[n - 1][0] ^= 1;
		diff -= 2;
		++cnt2;
		changed[n - 1][0] = true;
	}
	if (color[n - 1][n - 1] == c && diff - 2 >= 0) {
		color[n - 1][n - 1] ^= 1;
		diff -= 2;
		++cnt2;
		changed[n - 1][n - 1] = true;
	}

	// std::cout << "diff = " << diff << std::endl;
	// debug(diff);
	// debug(cnt2);
	// debug(cnt3);
	// debug(cnt4);
	// debug(free2);
	// debug(free3);
	// debug(free4);
	if (diff != 0 && diff != 1) {
		return false;
	}
	assert(diff == 0 || diff == 1);
	if (diff == 0) {
		return true;
	}

	if (cnt2 > 0 && cnt3 < free3) {
		if (changed[0][0]) {
			color[0][0] ^= 1;
		} else if (changed[0][n - 1]) {
			color[0][n - 1] ^= 1;
		} else if (changed[n - 1][0]) {
			color[n - 1][0] ^= 1;
		} else if (changed[n - 1][n - 1]) {
			color[n - 1][n - 1] ^= 1;
		} else {
			throw;
		}

		bool fl = false;
		for (int i = 1; i < n - 1; ++i) {
			if (!changed[0][i] && color[0][i] == c) {
				color[0][i] ^= 1;
				fl = true;
				break;
			} else if (!changed[i][0] && color[0][i] == c) {
				color[i][0] ^= 1;
				fl = true;
				break;
			} else if (!changed[i][n - 1] && color[0][i] == c) {
				color[i][n - 1] ^= 1;
				fl = true;
				break;
			} else if (!changed[n - 1][i] && color[0][i] == c) {
				color[n - 1][i] ^= 1;
				fl = true;
				break;
			} else {
				continue;
			}
		}

		assert(fl);
		return true;
	}
	if (cnt3 > 0 && cnt4 < free4) {
		bool fl = false;
		for (int i = 1; i < n - 1; ++i) {
			if (changed[0][i]) {
				color[0][i] ^= 1;
				fl = true;
				break;
			} else if (changed[i][0]) {
				color[i][0] ^= 1;
				fl = true;
				break;
			} else if (changed[i][n - 1]) {
				color[i][n - 1] ^= 1;
				fl = true;
				break;
			} else if (changed[n - 1][i]) {
				color[n - 1][i] ^= 1;
				fl = true;
				break;
			} else {
				continue;
			}
		}

		assert(fl);

		for (int i = 1; i < n - 1; ++i) {
			for (int j = 1; j < n - 1; ++j) {
				if (!changed[i][j] && color[i][j] == c) {
					color[i][j] ^= 1;
					return true;
				}
			}
		}

		throw;
	}
	if (free2 - cnt2 >= 2 && cnt3 > 0) {
		bool fl = false;
		// for (int i = 0; i < n; ++i) {
		// 	for (int j = 0; j < n; ++j) {
		// 		std::cout << color[i][j];
		// 	}
		// 	std::cout << std::endl;
		// }

		for (int i = 1; i < n - 1; ++i) {
			if (changed[0][i]) {
				color[0][i] ^= 1;
				fl = true;
				// std::cout << 0 << ' ' << i << std::endl;
				break;
			} else if (changed[i][0]) {
				color[i][0] ^= 1;
				fl = true;
				// std::cout << i << ' ' << 0 << std::endl;
				break;
			} else if (changed[i][n - 1]) {
				color[i][n - 1] ^= 1;
				fl = true;
				// std::cout << i << ' ' << n - 1 << std::endl;
				break;
			} else if (changed[n - 1][i]) {
				color[n - 1][i] ^= 1;
				fl = true;
				// std::cout << n - 1 << ' ' << i << std::endl;
				break;
			} else {
				continue;
			}
		}

		// for (int i = 0; i < n; ++i) {
		// 	for (int j = 0; j < n; ++j) {
		// 		std::cout << color[i][j];
		// 	}
		// 	std::cout << std::endl;
		// }

		assert(fl);

		int cntChanged = 0;
		if (!changed[0][0] && color[0][0] == c && cntChanged < 2) {
			color[0][0] ^= 1;
			++cntChanged;
		}
		if (!changed[0][n - 1] && color[0][n - 1] == c && cntChanged < 2) {
			color[0][n - 1] ^= 1;
			++cntChanged;
		}
		if (!changed[n - 1][0] && color[n - 1][0] == c && cntChanged < 2) {
			color[n - 1][0] ^= 1;
			++cntChanged;
		}
		if (!changed[n - 1][n - 1] && color[n - 1][n - 1] == c && cntChanged < 2) {
			color[n - 1][n - 1] ^= 1;
			++cntChanged;
		}

		assert(cntChanged == 2);
		return true;
	}
	if (cnt4 > 0 && free3 - cnt3 >= 1 && free2 - cnt2 >= 1) {
		bool fl = false;
		for (int i = 1; i < n - 1; ++i) {
			for (int j = 1; j < n - 1; ++j) {
				if (changed[i][j] && !fl) {
					color[i][j] ^= 1;
					fl = true;
				}
			}
		}

		int cntChanged = 0;
		if (!changed[0][0] && color[0][0] == c && cntChanged < 1) {
			color[0][0] ^= 1;
			++cntChanged;
		}
		if (!changed[0][n - 1] && color[0][n - 1] == c && cntChanged < 1) {
			color[0][n - 1] ^= 1;
			++cntChanged;
		}
		if (!changed[n - 1][0] && color[n - 1][0] == c && cntChanged < 1) {
			color[n - 1][0] ^= 1;
			++cntChanged;
		}
		if (!changed[n - 1][n - 1] && color[n - 1][n - 1] == c && cntChanged < 1) {
			color[n - 1][n - 1] ^= 1;
			++cntChanged;
		}

		assert(cntChanged == 1);

		fl = false;
		for (int i = 1; i < n - 1; ++i) {
			if (!changed[0][i] && color[0][i] == c) {
				color[0][i] ^= 1;
				fl = true;
				break;
			} else if (!changed[i][0] && color[0][i] == c) {
				color[i][0] ^= 1;
				fl = true;
				break;
			} else if (!changed[i][n - 1] && color[0][i] == c) {
				color[i][n - 1] ^= 1;
				fl = true;
				break;
			} else if (!changed[n - 1][i] && color[0][i] == c) {
				color[n - 1][i] ^= 1;
				fl = true;
				break;
			} else {
				continue;
			}
		}
		assert(fl);

		return true;
	}

	return false;
}

void solve(int n, int k) {
	if (n == 3 && k == 5) {
		for (int i = 0; i < 3; ++i) {
			color[0][i] = 1;
			color[2][i] = 0;
		}
		color[1][0] = 0;
		color[1][1] = 1;
		color[1][2] = 0;

		printf("Possible\n");
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (color[i][j] == 0) {
					printf("R");
				} else {
					printf("B");
				}
			}
			printf("\n");
		}
		return;
	}
	if (n == 3 && k == 7) {
		color[0][0] = 0;
		color[0][1] = 1;
		color[0][2] = 0;
		for (int i = 0; i < 3; ++i) {
			color[1][i] = 1;
		}
		color[2][0] = 1;
		color[2][1] = 0;
		color[2][2] = 1;

		printf("Possible\n");
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (color[i][j] == 0) {
					printf("R");
				} else {
					printf("B");
				}
			}
			printf("\n");
		}
		return;
	}

	if (k == 1 || k == 2 * n * (n - 1) - 1) {
		printf("Impossible\n");
		return;
	}

	for (int c = 0; c < 2; ++c) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				color[i][j] = (i + j) % 2;
			}
		}

		if (solve(n, k, c)) {
			printf("Possible\n");
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (color[i][j] == 0) {
						printf("R");
					} else {
						printf("B");
					}
				}
				printf("\n");
			}
			return;
		}
	}

	// printf("%d %d\n", n, k);
	printf("Impossible\n");
}

void run() {
	// for (int n = 1; n <= 50; ++n) {
	// 	for (int k = 0; k <= 2 * n * (n - 1); ++k) {
	// 		if (k == 1 || k == 2 * n * (n - 1) - 1) {
	// 			continue;
	// 		}
	// 		std::cout << n << ' ' << k << std::endl;
	// 		solve(n, k);

	// 		int cnt = 0;
	// 		for (int i = 0; i < n; ++i) {
	// 			for (int j = 0; j < n; ++j) {
	// 				if (i + 1 < n && color[i][j] != color[i + 1][j]) {
	// 					++cnt;
	// 				}
	// 				if (j + 1 < n && color[i][j] != color[i][j + 1]) {
	// 					++cnt;
	// 				}
	// 			}
	// 		}

	// 		assert(cnt == k);
	// 	}
	// }
    int t;
    scanf("%d", &t);

    while (t--) {
    	int n, k;
    	scanf("%d%d", &n, &k);

    	solve(n, k);
    }
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5684kb

input:

2
3 6
3 1

output:

Possible
BBR
BBB
RBR
Impossible

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 20ms
memory: 5872kb

input:

4424
1 0
2 4
2 3
2 2
2 1
2 0
3 12
3 11
3 10
3 9
3 8
3 7
3 6
3 5
3 4
3 3
3 2
3 1
3 0
4 24
4 23
4 22
4 21
4 20
4 19
4 18
4 17
4 16
4 15
4 14
4 13
4 12
4 11
4 10
4 9
4 8
4 7
4 6
4 5
4 4
4 3
4 2
4 1
4 0
5 40
5 39
5 38
5 37
5 36
5 35
5 34
5 33
5 32
5 31
5 30
5 29
5 28
5 27
5 26
5 25
5 24
5 23
5 22
5 21
5...

output:

Possible
R
Possible
RB
BR
Impossible
Possible
BB
BR
Impossible
Possible
BB
BB
Possible
RBR
BRB
RBR
Impossible
Possible
BBR
BRB
RBR
Possible
RRR
BRB
RBR
Possible
RBR
BBB
RBR
Possible
RBR
BBB
BRB
Possible
BBR
BBB
RBR
Possible
BBB
RBR
RRR
Possible
BBB
BBB
RBR
Possible
RRR
RRB
RRR
Possible
BBB
BBB
BBR
I...

result:

ok correct! (4424 test cases)

Test #3:

score: 0
Accepted
time: 20ms
memory: 9112kb

input:

1
1000 0

output:

Possible
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

result:

ok correct! (1 test case)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

1
1000 1

output:

Impossible

result:

ok correct! (1 test case)

Test #5:

score: 0
Accepted
time: 24ms
memory: 9464kb

input:

1
1000 1998000

output:

Possible
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #6:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

1
1000 1997999

output:

Impossible

result:

ok correct! (1 test case)

Test #7:

score: 0
Accepted
time: 24ms
memory: 9288kb

input:

1
1000 1638091

output:

Possible
BBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #8:

score: 0
Accepted
time: 24ms
memory: 9212kb

input:

1
1000 726743

output:

Possible
BBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #9:

score: 0
Accepted
time: 14ms
memory: 9016kb

input:

1
1000 1159802

output:

Possible
BBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #10:

score: 0
Accepted
time: 18ms
memory: 9060kb

input:

1
1000 1824691

output:

Possible
BBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #11:

score: 0
Accepted
time: 6ms
memory: 9272kb

input:

1
1000 1606348

output:

Possible
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (1 test case)

Test #12:

score: 0
Accepted
time: 24ms
memory: 6020kb

input:

100
100 3588
100 16278
100 14222
100 3818
100 16278
100 2672
100 7447
100 5705
100 9385
100 19205
100 16362
100 14175
100 327
100 18201
100 3519
100 14923
100 5358
100 17389
100 8773
100 7611
100 2185
100 3314
100 2358
100 18271
100 9499
100 12584
100 8079
100 16954
100 12620
100 16333
100 7148
100 ...

output:

Possible
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBR
RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

result:

ok correct! (100 test cases)

Test #13:

score: 0
Accepted
time: 18ms
memory: 6688kb

input:

10
280 56983
468 47999
111 964
346 192134
60 3108
348 98521
421 57292
24 310
29 1080
484 17366

output:

Possible
BBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB
BRBBBBBBBB...

result:

ok correct! (10 test cases)

Test #14:

score: 0
Accepted
time: 19ms
memory: 6728kb

input:

13
44 3612
468 9437
171 34192
174 33316
121 15295
249 1231
84 9464
170 56598
358 183525
369 42656
29 595
226 74474
296 34671

output:

Possible
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBR
RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB
BRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR
RBRBRBRBRBRBRBRBRBRBR...

result:

ok correct! (13 test cases)

Test #15:

score: 0
Accepted
time: 24ms
memory: 5840kb

input:

792
43 1432
33 1687
39 1872
49 906
41 27
49 1140
41 2730
39 1350
33 1625
26 986
26 1079
29 377
50 2930
24 536
28 874
44 1659
36 46
26 1199
46 1289
50 1662
48 59
20 90
37 2025
40 1971
31 443
31 511
36 1940
29 1515
21 104
24 432
23 337
38 2222
36 1016
24 786
23 737
50 1728
45 2032
22 183
50 416
44 375...

output:

Possible
RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBR
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBR
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
RBBBBBBBBBBBBBBBBBBBBBBBBBB...

result:

ok correct! (792 test cases)