QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168407 | #6644. Red Black Grid | ucup-team1209# | WA | 14ms | 9048kb | C++20 | 2.5kb | 2023-09-08 14:24:03 | 2023-09-08 14:24:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define templ template<typename T>
templ bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
#ifdef zqj
freopen("a.in","r",stdin);
#endif
}
typedef long long ll;
#define sz 1111
int n,K;
char a[sz][sz];
vector<pii>V[5];
map<pii,int>MP;
const int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void work() {
cin>>n>>K;
int _K=K;
if (K==1||K==2*n*(n-1)-1) return puts("Impossible"),void();
if (n<=4) {
if (!MP.count({n,K})) return puts("Impossible"),void();
rep(i,0,n*n-1) a[i/n+1][i%n+1]="RB"[MP[{n,K}]>>i&1];
}
else {
rep(i,2,4) V[i].clear();
rep(i,1,n) rep(j,1,n) if ((i+j)%2==0) {
int cc=0;
rep(t,0,3) {
int x=i+fx[t][0],y=j+fx[t][1];
if (x&&y&&x<=n&&y<=n) ++cc;
}
V[cc].push_back({i,j});
}
assert(V[2].size()>=2u&&V[3].size()&&V[4].size());
rep(i,1,n) rep(j,1,n) a[i][j]='B';
rep(t,2,4) {
while (V[t].size()>1u+(t==2)&&K-t>1) {
K-=t,a[V[t].back().fir][V[t].back().sec]='R';
V[t].pop_back();
}
}
vector<array<int,3>>vv;
rep(t,2,4) rep(i,0,t==2) vv.push_back({t,V[t][i].fir,V[t][i].sec});
int C=vv.size();
rep(s,0,(1<<C)-1) {
int cc=0;
rep(i,0,C-1) if (s>>i&1) cc+=vv[i][0];
if (cc==K) {
rep(i,0,C-1) if (s>>i&1) a[vv[i][1]][vv[i][2]]='R';
break;
}
}
}
rep(i,1,n) rep(j,1,n) if ((i+j)%2==0) {
rep(t,0,3) {
int x=i+fx[t][0],y=j+fx[t][1];
if (x&&y&&x<=n&&y<=n&&a[x][y]!=a[i][j]) --_K;
}
}
assert(!_K);
puts("Possible");
rep(i,1,n) cout<<a[i]+1<<'\n';
}
int main() {
file();
rep(n,1,4) {
static int a[5][5];
rep(s,0,(1<<(n*n))-1) {
rep(i,0,n*n-1) a[i/n+1][i%n+1]=s>>i&1;
int cc=0;
rep(i,1,n) rep(j,1,n) if ((i+j)%2==0) {
rep(t,0,3) {
int x=i+fx[t][0],y=j+fx[t][1];
if (x&&y&&x<=n&&y<=n&&a[x][y]!=a[i][j]) ++cc;
}
}
MP[{n,cc}]=s;
}
}
int T; cin>>T;
while (T--) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3412kb
input:
2 3 6 3 1
output:
Possible BRB RBB BBB Impossible
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 14ms
memory: 3432kb
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 B Possible BR RB Impossible Possible RB BB Impossible Possible BB BB Possible BRB RBR BRB Impossible Possible RBR BRB RBB Possible BRB RBR BBB Possible RBR BRB BBB Possible BBR RRB BBB Possible BRB RBB BBB Possible BBR RBB BBB Possible RBR BBB BBB Possible BRB BBB BBB Possible RBB BBB BBB I...
result:
ok correct! (4424 test cases)
Test #3:
score: 0
Accepted
time: 6ms
memory: 8732kb
input:
1 1000 0
output:
Possible BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
result:
ok correct! (1 test case)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
1 1000 1
output:
Impossible
result:
ok correct! (1 test case)
Test #5:
score: 0
Accepted
time: 11ms
memory: 8268kb
input:
1 1000 1998000
output:
Possible RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #6:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
1 1000 1997999
output:
Impossible
result:
ok correct! (1 test case)
Test #7:
score: 0
Accepted
time: 9ms
memory: 9048kb
input:
1 1000 1638091
output:
Possible RBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #8:
score: 0
Accepted
time: 11ms
memory: 8120kb
input:
1 1000 726743
output:
Possible RBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #9:
score: 0
Accepted
time: 12ms
memory: 9024kb
input:
1 1000 1159802
output:
Possible RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #10:
score: 0
Accepted
time: 8ms
memory: 8288kb
input:
1 1000 1824691
output:
Possible RBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #11:
score: 0
Accepted
time: 8ms
memory: 9028kb
input:
1 1000 1606348
output:
Possible BBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR...
result:
ok correct! (1 test case)
Test #12:
score: 0
Accepted
time: 12ms
memory: 3744kb
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 BBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBR RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
result:
ok correct! (100 test cases)
Test #13:
score: -100
Wrong Answer
time: 8ms
memory: 4672kb
input:
10 280 56983 468 47999 111 964 346 192134 60 3108 348 98521 421 57292 24 310 29 1080 484 17366
output:
Possible RBBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB BBBBBBBBBB...
result:
wrong answer Condition failed: "A.length() == n" (test case 3)