{"problem":{"name":"Two Rooms","description":{"content":"There are $N$ people numbered $1,2,\\ldots,N$. For $i\\neq j$, the intimacy between persons $i$ and $j$ is $A_{i,j}$. For each of the $N$ people, assign room $X$ or room $Y$. Each of the $N$ people move","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc212_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ people numbered $1,2,\\ldots,N$. For $i\\neq j$, the intimacy between persons $i$ and $j$ is $A_{i,j}$.\nFor each of the $N$ people, assign room $X$ or room $Y$. Each of the $N$ people moves to their assigned room. It is acceptable if there is an empty room.\nPerson $i$ is in a **good state** if the following is satisfied:\n\n> (Sum of intimacy with person $i$ of all people in the same room as person $i$) $\\geq$ (Sum of intimacy with person $i$ of all people in a different room from person $i$).\n\nOutput one assignment of rooms such that all $N$ people are in a good state.\nIt can be proved that such an assignment always exists.\n\n## Constraints\n\n*   $2 \\leq N \\leq 50$\n*   $-50 \\leq A_{i,j} \\leq 50$\n*   $A_{i,j} = A_{j,i}$\n*   $A_{i,i}=0$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_{1,1}$ $A_{1,2}$ $\\cdots$ $A_{1,N}$\n$A_{2,1}$ $A_{2,2}$ $\\cdots$ $A_{2,N}$\n$\\vdots$\n$A_{N,1}$ $A_{N,2}$ $\\cdots$ $A_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc212_d","tags":[],"sample_group":[["4\n0 4 -2 -1\n4 0 -3 -5\n-2 -3 0 2\n-1 -5 2 0","XXYY\n\nSuppose persons $1,2$ are assigned to room $X$ and persons $3,4$ are assigned to room $Y$.\nFor person $1$, the sum of intimacy with people in the same room (person $2$) is $4$, and the sum of intimacy with people in different rooms (persons $3$ and $4$) is $(-2)+(-1)=-3$, so they are in a good state.\nAll other people are also in a good state, so this assignment satisfies the condition.\nOutputting `YYXX` is also correct."],["3\n0 0 0\n0 0 0\n0 0 0","XXX\n\nIt is acceptable if there is an empty room."]],"created_at":"2026-03-03 11:01:13"}}