# 某島

… : "…アッカリ～ン . .. . " .. .
April 5, 2020

## Google Code Jam 2020 Qualification Round

ABC 略。

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
n = list(map(int, input().split()))[0]
A = []
for i in range(n):
A.append(list(map(int, input().split())))

k = 0
r = 0
c = 0
for i in range(n):
k += A[i][i]

for i in range(n):
C = [0] * (n+1)
for j in range(n):
if (C[A[i][j]] == 1):
r += 1
break
C[A[i][j]] = 1

for j in range(n):
C = [0] * (n+1)
for i in range(n):
if (C[A[i][j]] == 1):
c += 1
break
C[A[i][j]] = 1

print("Case #%d: %d %d %d" % (case, k,r,c))

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
s = input()
z = ""
k = 0
for c in s:
while (k < int(c)):
z += '('
k += 1
while (k > int(c)):
z += ')'
k -= 1
z += c
while (k > 0):
z += ')'
k -= 1

print("Case #%d: %s" % (case, z))

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
n = list(map(int, input().split()))[0]
e = []
z = ['-'] * n
o = list(range(n))
for i in range(n):
e.append(list(map(int, input().split())))

o.sort(key=lambda x: e[x])
t = 0
for _i in range(n):
i = o[_i]
if (z[i] == '-' and e[i][0] >= t):
z[i] = 'C'
t = e[i][1]
t = 0
for _i in range(n):
i = o[_i]
if (z[i] == '-' and e[i][0] >= t):
z[i] = 'J'
t = e[i][1]

res = ""
for i in range(n):
res += z[i]
for i in range(n):
if (z[i] == '-'):
res = "IMPOSSIBLE"
break
print("Case #%d: %s" % (case, res))

D 交互題。

—– xxxxx xxxxx —–

– 相同的話，取反 和 取反加交換，會改變這兩個元素的狀態。
– 不同的話，取反 和 交換，會改變這兩個元素的狀態。

int A[N], B[N];
VI t00[N], t01[N]; int same[N];

void query(int A[], int x) {
cout << x << endl;  cout.flush();
cin >> A[x];
}

int main() {

#ifndef ONLINE_JUDGE
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif

// 0 0 ,       rev, swap rev
// 0 1 , swap, rev

// 100
// 20

int t, n; RD(t, n); REP(ii, t) {

REP(i, n/10) {
t00[i].clear(); t01[i].clear();
REP_1(j, 5) {
int a = i*10+j;
int b = n+1-a;
query(A, a);
query(A, b);
if (A[a] == A[b]) {
t00[i].PB(a);
} else {
t01[i].PB(a);
}
}
}

REP(i, n/10) {
//if (t00[i].empty() || t01[i].empty()) continue;
int a0 = t00[i].empty() ? t01[i].front() : t00[i].front();
int a1 = t01[i].empty() ? t00[i].front() : t01[i].front();
query(B, a0);
query(B, a1);

same[i] = (A[a0]==B[a0]) == (A[a1]==B[a1]);
}

REP(i, n/10) {

if (!t00[i].empty()) {
int a = t00[i].front();
query(B, a);
if (A[a] != B[a]) {
for (auto a: t00[i]) {
int b = n+1 - a;
A[a] ^= 1;
A[b] ^= 1;
}

if (same[i]) {
for (auto a: t01[i]) {
int b = n+1 - a;
A[a] ^= 1;
A[b] ^= 1;
}
}
} else {
if (!same[i]) {
for (auto a: t01[i]) {
int b = n+1 - a;
A[a] ^= 1;
A[b] ^= 1;
}
}
}
} else {
int a = t01[i].front();
query(B, a);
if (A[a] != B[a]) {
for (auto a: t01[i]) {
int b = n+1 - a;
A[a] ^= 1;
A[b] ^= 1;
}
}
}
}

string s;
REP_1(i, n) {
s += char('0' + A[i]);
}

cout << s << endl; cout.flush(); cin >> s;
}
}

const int N = (1e2) + 9;
int A[N][N];
int n, k;

bool dfs(int x = 0, int y = 0) {
if (x == n) {
int s = 0;
REP(i, n) s += A[i][i];
if (s == k) {
puts("POSSIBLE");
REP(i, n) {
REP(j, n) printf("%d ", A[i][j]);
cout << endl;
}
return 1;
}
return 0;
}
if (y == n) {
return dfs(x+1, 0);
}

VI t; REP(i, n+1) t.PB(1);
REP(i, x) t[A[i][y]] = 0;
REP(i, y) t[A[x][i]] = 0;
REP_1(i, n) if (t[i]) {
A[x][y] = i;
if (dfs(x, y+1)) {
return 1;
}
}
return 0;
}

int main() {

#ifndef ONLINE_JUDGE
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif

// 0 0 ,       rev, swap rev
// 0 1 , swap, rev

// 100
// 20

int T; RD(T); REP_1(Case, T) {

printf("Case #%d: ", Case);
RD(n,k);

if (!dfs()) {
puts("IMPOSSIBLE");
}
}
}