QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124623#4327. ŠeširiHe_Ren100 ✓225ms149092kbC++171.6kb2023-07-15 10:59:162023-07-15 10:59:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 10:59:17]
  • 评测
  • 测评结果:100
  • 用时:225ms
  • 内存:149092kb
  • [2023-07-15 10:59:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int ALL = (1<<19) + 5;
const int MAXE = ALL * 18;

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

struct Edge
{
	int next,to,res;
}e[MAXE];
int head[ALL], etot = -1;
inline void add_one(int u,int v)
{
	e[++etot] = (Edge){ head[u],v,-1};
	head[u] = etot;
}
inline void add_edge(int u,int v)
{
	add_one(u,v); add_one(v,u);
}

int id[ALL][18];

int cur[ALL];
bool vis[ALL];

void dfs(int u)
{
	vis[u] = 1;
	for(int &i=cur[u]; ~i; i=e[i].next)
	{
		if(e[i].res != -1) continue;
		int v = e[i].to;
		e[i].res = 1;
		e[i^1].res = 0;
		dfs(v);
	}
}

int main(void)
{
	int n;
	scanf("%d",&n);
	
	int pcnt = (1<<n) * 2 + 1;
	
	memset(head, -1, sizeof(head));
	for(int i=0; i<(1<<n); ++i)
	{
		int cnt[2] = {0,0};
		for(int k=0; k<n; ++k)
		{
			int x = bdig(i, k);
			++cnt[x];
			if(x == 1) continue;
			
			int j = i ^ bbit(k);
			id[i][k] = etot + 1;
			add_edge(i << 1 | 0, j << 1 | 1);
		}
		if(cnt[0] & 1)
			add_edge(i << 1 | 0, pcnt - 1);
		if(cnt[1] & 1)
			add_edge(i << 1 | 1, pcnt - 1);
	}
	
	memcpy(cur, head, sizeof(head));
	for(int i=0; i<pcnt; ++i) if(!vis[i])
		dfs(i);
	
	static int ans[18][ALL];
	for(int i=0; i<(1<<n); ++i)
		for(int k=0; k<n; ++k) if(!bdig(i, k))
		{
			int mask = 0;
			for(int kk=0; kk<n; ++kk) if(kk != k)
				mask = mask << 1 | bdig(i, kk);
			ans[k][mask] = e[id[i][k]].res;
		}
	
	for(int i=0; i<n; ++i, printf("\n"))
		for(int j=0; j<(1<<(n-1)); ++j)
			putchar(ans[i][j] + 'B');
	return 0;
}

详细

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 1ms
memory: 18928kb

input:

4

output:

BCBCCBCC
CBCBBCBB
BCBCCBCC
CBCBBCBB

result:

ok good plan!

Subtask #2:

score: 7
Accepted

Test #2:

score: 7
Accepted
time: 0ms
memory: 20136kb

input:

5

output:

BBCCBBCCCBBBBBCB
CCBBCBBBBCBCCCBC
BBCBBBCCCBCBBBCB
CCBCCCBCBCBBCCBC
BBCBBBCBCBCCBBCB

result:

ok good plan!

Subtask #3:

score: 7
Accepted

Test #3:

score: 7
Accepted
time: 1ms
memory: 22372kb

input:

6

output:

BCBCCCBCBCBCCCCCCBCBBBBBCCBCCBCC
CBCBBBCBCBCBBBBBBCBCCCCCBBCBBCBB
BCBCCBCCBCBCCCCCCBCBBBBBCCBCCBCC
CBCBBBCBCBCCBBCBBBCBCCBCBBCBBCBB
BCBCCCBCBCBCCCBCCCBCBCCBCCBCCBCC
CBCBBBCBCBCBBBCBBBCBCBBCBBCBBCBB

result:

ok good plan!

Subtask #4:

score: 7
Accepted

Test #4:

score: 7
Accepted
time: 0ms
memory: 25232kb

input:

7

output:

BBCCBCCBCBCCCBCCBBBCCCCBCCCCCBCCCBBBBBBBBBBBBBBBBBCBBBBCCBBBBBCB
CCBBCBBCBBBBBCBBCBBBBBBBBBBBBBBBBCBCCCCCBCCCCCCCCCBBCBBBBCBCCCBC
BBCCBBCBCBBCCBCBBBCCBCCCCCCBCBCCCBCBBBBBCBBBBBBBBBCCBCCCCBCBBBCB
CCBBCBBCBCCBBCBCCCBCCBCBBCBCCCBBBCBBCCBCBBCCBCCCCCBBCBBBBCBCCCBC
BBCBBCCBCBCCCBCBBBCBBBCCCBCBBBCCCBCCBBCB...

result:

ok good plan!

Subtask #5:

score: 7
Accepted

Test #5:

score: 7
Accepted
time: 1ms
memory: 26332kb

input:

8

output:

BCBCCCBCBCBCCCBCCBBBCBCCBCBBCCCCBBBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBCBBBBBCBBCBBCBBBBBBBCBBBCBBBBBCCBCCBBCBBBCCCCCCBCBBBBBCCBCCBCC
CBCBBBCBCBCBBBCBBBCCBCBBCBCCBBBBCBCBBBBBCBBCBBBBBBBBBBCBBBCBBBBBBCBCCCCCBCCBCCBCCCCCCCCCCCBCCCCCBBCBBBBBCBCBBBBBBCBCCCCCBBCBBCBB
BCBCCCCCBCBCCCBCCBCBBBCBCCBCCBCCBCBCCCCCBC...

result:

ok good plan!

Subtask #6:

score: 7
Accepted

Test #6:

score: 7
Accepted
time: 1ms
memory: 28968kb

input:

9

output:

BBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCCCBBCCCCBCCCCCBCBCBCCBCCBCBCCCBCCBBBCBCCBCCCBCBCCCCCCCBCCCBBCCCCBCCCCCBCBCBCCCBCCCBBCCCCBCCCCCBCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBBBBBBBBBBBBBBBBCBBBBBCBBCBBCBBBBCBCCBBCCBCBBCCBBBBBBBBBBBBBBBBBCBBBBCCBBBBBCB
CCBBCBBCBBBBBCBBCBBCBCCBBCCBCBBBBBBBBBBBBBB...

result:

ok good plan!

Subtask #7:

score: 7
Accepted

Test #7:

score: 7
Accepted
time: 1ms
memory: 31180kb

input:

10

output:

BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCCBBBBBCBBBCBCBCBCBCCCCCBCCCBCBBCBCBBCCBCBCBCBCBBCBCBCBCCCCBCCCCCBBBCBCCBBCCBCBCCCCCCCCBCCCBCCCCCBCCBCCBCCCCCBCCBCBBCCCCCCCCCCCCCCCCCCCBCCCCCCCBCCBBBCBCCBCBBCCCCCBBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBCBBBBBCBBCBBCBBBBBBBCBBBCBBBBBCBBCBBCBBBBB...

result:

ok good plan!

Subtask #8:

score: 7
Accepted

Test #8:

score: 7
Accepted
time: 0ms
memory: 33784kb

input:

11

output:

BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBBCBBCBBCCCBBCBCCCBBCCCCCCCBBCBCCCBCCCCCCCBBCCCCCCCCCCCCCCCBBCCCCBBCCBCBBBCCCCCBCBCBBBCBBBCCCCCBCBCBCBCBBCCBBBCBBBCBBCBBCBCBCCBCCBCBCCCBCCBBCBCBBCCBBCBCCCCBBCCCCBCCCCCBCBCBCCBCCBCBCCCBCCBBBCBCCBBCCBCBBCCCCBCBCCCBBCCCCBCCCCCBCCCBBC...

result:

ok good plan!

Subtask #9:

score: 7
Accepted

Test #9:

score: 7
Accepted
time: 1ms
memory: 37368kb

input:

12

output:

BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCBBBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBBBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCBCBBBCBCBCBCBCCBBBCCCCCCCCCCCCCCCCBCBCBCBCBCCCCCBCBBCBCCBCCBCCCCBCBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBBBBBCBBBCBCBCBBBCBCBCBCBCBBBBBBBCBCCCBCCCB...

result:

ok good plan!

Subtask #10:

score: 7
Accepted

Test #10:

score: 7
Accepted
time: 2ms
memory: 40936kb

input:

13

output:

BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCCCBBCCCCBCCCCCBCCCCCCCCCCCBCCCCCCCCCCCCCCCCCCCCCCCBCCCCCCCCCCCCCBCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBBBCBBBCBBCBBCCCBBCBBCCBBCCCCCBCBBCBCCCBBCC...

result:

ok good plan!

Subtask #11:

score: 6
Accepted

Test #11:

score: 6
Accepted
time: 5ms
memory: 43580kb

input:

14

output:

BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBCBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCCBCBBBCBBBCBCBCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...

result:

ok good plan!

Subtask #12:

score: 6
Accepted

Test #12:

score: 6
Accepted
time: 20ms
memory: 52228kb

input:

15

output:

BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBBCBBCBBCBCBBCBCCBBBCBCBBCCBBCBCCBBCCB...

result:

ok good plan!

Subtask #13:

score: 6
Accepted

Test #13:

score: 6
Accepted
time: 42ms
memory: 66632kb

input:

16

output:

BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBBBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCBCBCBCCCBCCCCCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...

result:

ok good plan!

Subtask #14:

score: 6
Accepted

Test #14:

score: 6
Accepted
time: 86ms
memory: 89604kb

input:

17

output:

BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCBBBBCBCBBBCCBCBBCCBBCBCCBBCCB...

result:

ok good plan!

Subtask #15:

score: 6
Accepted

Test #15:

score: 6
Accepted
time: 225ms
memory: 149092kb

input:

18

output:

BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBBBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCCBCCCCCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...

result:

ok good plan!

Extra Test:

score: 0
Extra Test Passed