QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#680528#7900. Gifts from KnowledgeSCAU_xyjkanadeWA 18ms7952kbC++203.0kb2024-10-26 21:23:132024-10-26 21:23:15

Judging History

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

  • [2024-10-26 21:23:15]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:7952kb
  • [2024-10-26 21:23:13]
  • 提交

answer

#include <bits/stdc++.h>/////奇数要处理 
using namespace std;
const long long MOD = 1e9 + 7;
const int N = 2e6 + 10;
int T;
vector <int> v[N];
int n,m;
string s;
vector <int> p[N];
map <int,int> mp;
int vis[N];
struct edge
{
	int id;
	int val;
};
queue <edge> q;
int vis_point[N];
int bfs(int x)
{
	while(!q.empty())q.pop();
	vis[x] = 1;
	int siz = v[x].size();
	for(int i = 0;i < siz;i++)
		q.push({x,v[x][i]});
	int flag = 1;
	while(!q.empty())
	{
		if(!flag)break;
		edge u = q.front();
		vis_point[u.val] = 1;
		vis[u.id] = 1;
		q.pop();
		int ts = p[u.val].size();
		if(ts == 1){
			if(!flag)break;
			continue;
		}
		if(ts == 2){
			if(!flag)break;
			int pp = p[u.val][0] + p[u.val][1] - u.id;
			if(!vis[pp])
			{
				vis[pp] = 1;
				int id = lower_bound(v[pp].begin(),v[pp].end(),u.val) - v[pp].begin();	
				if(v[pp][id] != u.val){
					int tz = v[pp].size();
					for(int i = 0;i < tz;i++)
					{
						if(vis_point[v[pp][i]]){
							flag = 0;
							break;
						}
						else
						{
							vis_point[v[pp][i]] = 1;
							q.push({pp,v[pp][i]});
						}
					}
				}
				else
				{
					int tz = v[pp].size();
					for(int i = 0;i < tz;i++)
					{
						int xx = (m + 1) - v[pp][i];
						if(vis_point[xx]){
							flag = 0;
							break;
						}
						else
						{
							vis_point[xx] = 1;
							q.push({pp,xx});
						}
					}
				}
			}  
		}
	}
	if(!flag || !q.empty())return 0;
	else return 1;
}
long long qpow(int x)
{
	long long ret = 1,k = 2;
	while(x)
	{
		if(x % 2 == 1)
			ret *= k,ret %= MOD;
		x /= 2;
		k *= k;
		k %= MOD;
	}
	return ret;
}
void init(int x,int y)
{
	for(int i = 0;i <= x;i++)
		{
			vis[i] = 0;
			v[i].clear();
		}
		for(int i = 0;i <=y;i++)
		{
			vis_point[i] = 0;
			p[i].clear();
		}
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> T;
	while(T--)
	{
		init(n,m);
		int cnt = 0;
		cin >> n >> m;
		for(int i = 1;i <= n;i++){
			cin >> s;
			for(int j = 0;j < m;j++)
			{
				if(s[j] == '1'){
					if(m % 2 == 1 && j + 1 == m / 2 + 1){
						cnt++;
					}
					else{
					v[i].push_back(j + 1);
					p[j + 1].push_back(i);
					p[(m + 1) - (j + 1)].push_back(i);}
				}
			}
		}
		if(cnt > 1){
			cout << 0 << endl;
			init(n,m);
			continue;
		}
		int flag = 1;
		//cout << "fuck you data" << endl;
		for(int i = 1;i <= m;i++)
		{	
			if(p[i].size() > 2){
				//cout << i << " " << p[i].size() << endl;
				//for(int j = 0;j < p[i].size();j++)cout << p[i][j] << " ";
				//cout << endl;
				flag = 0;
				break;
			}
		}	
		if(!flag){
			cout << 0 << endl;
			init(n,m); 
			continue;
		}
		int ans = 0;
		//cout << "fuck you data" << endl;
		for(int i = 1;i <= n;i++)
		{
			if(!vis[i]){
				int pd = bfs(i);
				if(pd)ans++;
				else {
					ans = -1;
					break;
				}
			}
		}
		if(!flag){
			cout << 0 << endl;
			init(n,m);
			continue;
		}
		if(ans == -1)cout << 0 << endl;
		else cout << qpow(ans) << endl;
		init(n,m);
	}	
	return 0;
} 

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7728kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

4
0
2

result:

ok 3 number(s): "4 0 2"

Test #2:

score: 0
Accepted
time: 18ms
memory: 7952kb

input:

15613
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
15 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
1 5
00000
5 9
000000000
000000000
0000...

output:

1024
32768
2
32
32768
128
32
16
16
2
16384
16384
128
128
32768
8192
128
64
16384
2
4
2
4096
16
4096
1024
32768
32768
16384
8
128
2
16
4096
8192
32768
8192
8192
16
16384
16384
256
128
8
256
8
4096
512
2
4
32
32
2
64
512
1024
32768
32768
2
64
16384
16
8192
16
256
16
64
8192
8192
64
1024
2
32768
2
4
51...

result:

ok 15613 numbers

Test #3:

score: -100
Wrong Answer
time: 11ms
memory: 7752kb

input:

15759
9 6
000000
000000
000000
000000
000000
000000
000000
000000
000000
5 15
010000000000000
000000000000000
000000000000000
000100000000000
000100000000000
14 12
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000...

output:

512
16
16384
512
1024
4096
32768
4
2
512
512
512
512
8
2
256
16
4096
512
64
16
4096
512
32
32768
8192
32
2048
128
16
4096
64
32768
256
32
16384
8
512
32
2048
8
16
1024
2048
128
64
32
8
512
8
8192
256
8192
32768
2
8
512
512
256
32
2
2048
8192
8
64
8
2
16384
32768
32768
1024
4096
16384
16384
128
256
4...

result:

wrong answer 1293rd numbers differ - expected: '64', found: '0'