QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509599#9170. Cycle GamePhantomThreshold#WA 0ms3752kbC++201.7kb2024-08-08 16:28:502024-08-08 16:28:51

Judging History

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

  • [2024-08-08 16:28:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3752kb
  • [2024-08-08 16:28:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<int>> a(n+5,vector<int>(m+5));
	vector<int> pa(n*m+5);
	int C=0,V=0,E=0,S=0;
	auto hs=[&](int x,int y){return (x-1)*m+y;};
	auto inb=[&](int x,int y){return 1<=x and x<=n and 1<=y and y<=m;};
	function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
	vector<int> ans(k+5);
	for(int tt=1;tt<=k;tt++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
		int tC=C,tV=V,tE=E,tS=S;
		tC++;
		vector<int> pC;
		tV++;
		if(inb(x-1,y) and a[x-1][y])tE++,pC.emplace_back(find(hs(x-1,y)));
		if(inb(x,y-1) and a[x][y-1])tE++,pC.emplace_back(find(hs(x,y-1)));
		if(inb(x+1,y) and a[x+1][y])tE++,pC.emplace_back(find(hs(x+1,y)));
		if(inb(x,y+1) and a[x][y+1])tE++,pC.emplace_back(find(hs(x,y+1)));
		for(int i=max(x-1,1);i+1<=min(x+1,n);i++)
			for(int j=max(y-1,1);j+1<=min(y+1,m);j++)
			{
				if(a[i][j] and a[i+1][j] and a[i][j+1] and a[i+1][j+1])
					tS++;
			}
		sort(pC.begin(),pC.end());
		pC.erase(unique(pC.begin(),pC.end()),pC.end());
		tC-=(int)pC.size();
//		cerr<<"!! "<<tE<<' '<<tV<<' '<<tS<<' '<<tC<<' '<<tE-tV-tS+tC<<endl;
		if(tE-tV-tS+tC==0)
		{
			ans[tt]=1;
			E=tE;V=tV;S=tS;C=tC;
			auto merge=[&](int u,int v)
			{
				int pu=find(u),pv=find(v);
				if(pu!=pv)pa[pv]=pu;
			};
			if(inb(x-1,y) and a[x-1][y])merge(hs(x-1,y),hs(x,y));
			if(inb(x,y-1) and a[x][y-1])merge(hs(x,y-1),hs(x,y));
			if(inb(x+1,y) and a[x+1][y])merge(hs(x+1,y),hs(x,y));
			if(inb(x,y+1) and a[x][y+1])merge(hs(x,y+1),hs(x,y));
		}
		else
		{
			a[x][y]=0;
		}
	}
	for(int i=1;i<=k;i++)
		cout<<ans[i];
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

output:

1111111

result:

ok "1111111"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

3 3 8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

output:

11111110

result:

ok "11111110"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

10 10 7
9 1
6 6
3 8
8 7
5 10
1 7
1 2

output:

1111111

result:

ok "1111111"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

9 10 50
1 9
1 6
2 3
3 1
7 4
9 4
1 3
2 5
9 2
7 9
5 6
8 10
9 5
5 5
4 10
9 7
5 9
3 2
4 5
1 1
4 7
3 6
2 8
4 3
8 6
5 10
4 8
5 4
7 2
9 6
4 2
7 8
5 2
3 5
9 1
6 1
1 5
9 9
5 8
6 3
8 8
8 4
7 7
7 1
3 7
2 2
3 10
6 9
8 3
7 6

output:

11111111111111111111111111111111111111111111111111

result:

ok "11111111111111111111111111111111111111111111111111"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

3 5 11
1 5
2 4
1 2
1 3
3 3
3 1
3 4
2 3
1 4
2 1
2 5

output:

11111111111

result:

ok "11111111111"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

7 9 12
7 3
2 3
6 2
2 2
4 2
2 8
5 7
4 4
6 8
2 7
7 2
1 9

output:

111111111111

result:

ok "111111111111"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3596kb

input:

9 8 67
5 5
8 3
9 5
7 4
5 1
9 3
4 2
2 5
1 7
7 8
7 2
8 5
6 1
8 8
4 4
5 4
1 5
3 4
6 7
2 3
3 7
5 7
2 4
2 7
1 3
7 3
2 8
6 6
6 2
6 3
7 5
9 6
7 6
3 6
1 1
6 4
3 1
5 3
8 7
2 1
4 1
8 4
8 6
3 5
5 8
1 6
1 2
4 6
9 4
1 4
3 3
4 8
8 1
4 7
9 8
3 8
6 5
6 8
3 2
2 2
7 1
9 2
4 3
1 8
4 5
8 2
7 7

output:

1111111111111111111111111111111111111111111110011111101010001101111

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111110010101101000101101101', found: '111111111111111111111111111111...1111111110011111101010001101111'