QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168407#6644. Red Black Griducup-team1209#WA 14ms9048kbC++202.5kb2023-09-08 14:24:032023-09-08 14:24:04

Judging History

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

  • [2023-09-08 14:24:04]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:9048kb
  • [2023-09-08 14:24:03]
  • 提交

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)