QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22474#2353. Maharajas are Going HomeDaBenZhongXiaSongKuaiDi#WA 831ms28240kbC++202.7kb2022-03-09 19:00:122022-04-30 01:10:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:10:20]
  • 评测
  • 测评结果：WA
  • 用时：831ms
  • 内存：28240kb
查看
  • [2022-03-09 19:00:12]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
bitset<6005>h[4005],l[4005],dj[4005],tmp;
int sg[2005][2005];
int tx[4005],ty[4005];
int main()
{
	int ans=0;
	for(int i=1;i<=4000;i++)
	{
		h[i].set();
		l[i].set();
		dj[i].set();
	}
	for(int i=1;i<=2000;i++)
	{
		for(int j=1;j<=2000;j++)
		{
			tmp.set();
			tmp=tmp&h[i];
			tmp=tmp&l[j];
			tmp=tmp&dj[i-j+2000];
			if(i>=3&&j>=2)tmp[sg[i-2][j-1]]=0;
			if(i>=2&&j>=3)tmp[sg[i-1][j-2]]=0;
			sg[i][j]=tmp._Find_first();
			h[i][sg[i][j]]=0;
			l[j][sg[i][j]]=0;
			dj[i-j+2000][sg[i][j]]=0;
		}
	}
	/*for(int i=1;i<=25;i++)
	{
		for(int j=1;j<=25;j++)
		{
			printf("%d ",sg[i][j]);
		}
		printf("\n");
	}*/
	int t,k,yh,sth;
	int ansx,ansy;
	t=read();
	bool flag;
	for(int greg=1;greg<=t;greg++)
	{
		yh=0;
		k=read();
		for(int i=1;i<=k;i++)
		{
			tx[i]=read();
			ty[i]=read();
			yh^=sg[tx[i]][ty[i]];
		}
		if(yh==0)
		{
			printf("-1 -1 -1\n");
			continue;
		}
		sth=0;
		for(int i=1;i<=k;i++)
		{
			if((sg[tx[i]][ty[i]]^yh)<sg[tx[i]][ty[i]])
			{
				sth=i;
				break;
			}
		}
		ansx=tx[sth];
		ansy=ty[sth];
		//printf("%d\n",sth);
		flag=false;
		for(int i=1;i<=tx[sth]-1;i++)
		{
			if(sg[i][ty[sth]]==(yh^sg[tx[sth]][ty[sth]]))
			{
				if(i<ansx)
				{
					ansx=i;
					ansy=ty[sth];
				}
			}
		}
		if(flag==true)continue;
		for(int i=1;i<=ty[sth]-1;i++)
		{
			if(sg[tx[sth]][i]==(yh^sg[tx[sth]][ty[sth]]))
			{
				if(tx[sth]<ansx||(tx[sth]==ansx&&i<ansy))
				{
					ansx=tx[sth];
					ansy=i;
				}
			}
		}
		if(flag==true)continue;
		for(int i=1;i<=min(tx[sth],ty[sth])-1;i++)
		{
			if(sg[tx[sth]-i][ty[sth]-i]==(yh^sg[tx[sth]][ty[sth]]))
			{
				if(tx[sth]-i<ansx||(tx[sth]-i==ansx&&ty[sth]-i<ansy))
				{
					ansx=tx[sth]-i;
					ansy=ty[sth]-i;
				}
			}
		}
		if(flag==true)continue;
		if(tx[sth]>=3&&ty[sth]>=2)
		{
			//printf("orz%d %d %d\n",sg[tx[sth]-2][ty[sth]-1],yh,sg[tx[sth]][ty[sth]]);
			if(sg[tx[sth]-2][ty[sth]-1]==(yh^sg[tx[sth]][ty[sth]]))
			{
				if(tx[sth]-2<ansx||(tx[sth]-2==ansx&&ty[sth]-1<ansy))
				{
					ansx=tx[sth]-2;
					ansy=ty[sth]-1;
				}
			}
		}
		if(flag==true)continue;
		if(tx[sth]>=2&&ty[sth]>=3)
		{
			if(sg[tx[sth]-1][ty[sth]-2]==(yh^sg[tx[sth]][ty[sth]]))
			{
				if(tx[sth]-1<ansx||(tx[sth]-1==ansx&&ty[sth]-2<ansy))
				{
					ansx=tx[sth]-1;
					ansy=ty[sth]-2;
				}
			}
		}
		printf("%d %d %d\n",sth,ansx,ansy);
	}
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 803ms
memory: 28156kb

input:

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

output:

3 1 1
-1 -1 -1
2 1 1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 789ms
memory: 28196kb

input:

1
1
1 1

output:

-1 -1 -1

result:

ok single line: '-1 -1 -1'

Test #3:

score: 0
Accepted
time: 831ms
memory: 28124kb

input:

100
1
5 5
1
1 5
1
5 4
1
4 4
1
2 2
1
5 3
1
4 5
1
2 4
1
4 1
1
3 2
1
3 2
1
1 4
1
2 5
1
4 2
1
5 3
1
5 5
1
4 2
1
3 4
1
3 4
1
4 2
1
3 1
1
1 5
1
1 4
1
4 1
1
4 5
1
2 5
1
5 1
1
4 1
1
2 4
1
2 5
1
3 4
1
2 5
1
5 4
1
4 4
1
2 3
1
3 4
1
5 4
1
1 3
1
3 4
1
1 5
1
5 1
1
2 3
1
3 1
1
1 1
1
5 2
1
2 5
1
1 4
1
3 3
1
4 3
1
...

output:

1 1 1
1 1 1
1 2 4
1 1 1
1 1 1
1 4 2
1 2 4
-1 -1 -1
1 1 1
1 1 1
1 1 1
1 1 1
1 2 4
-1 -1 -1
1 4 2
1 1 1
-1 -1 -1
1 2 4
1 2 4
-1 -1 -1
1 1 1
1 1 1
1 1 1
1 1 1
1 2 4
1 2 4
1 1 1
1 1 1
-1 -1 -1
1 2 4
1 2 4
1 2 4
1 2 4
1 1 1
1 1 1
1 2 4
1 2 4
1 1 1
1 2 4
1 1 1
1 1 1
1 1 1
1 1 1
-1 -1 -1
1 4 2
1 2 4
1 1 1
...

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 770ms
memory: 28240kb

input:

100
1
10 10
1
9 8
1
2 5
1
9 10
1
3 6
1
1 2
1
1 2
1
10 6
1
6 4
1
10 8
1
7 1
1
1 3
1
4 2
1
2 1
1
1 5
1
10 4
1
6 7
1
7 2
1
7 1
1
10 2
1
4 1
1
9 3
1
9 8
1
2 2
1
2 3
1
1 9
1
3 3
1
3 9
1
9 4
1
2 2
1
6 8
1
1 3
1
3 10
1
7 6
1
10 10
1
7 8
1
2 7
1
5 3
1
8 6
1
4 4
1
9 5
1
5 1
1
2 1
1
4 1
1
3 1
1
1 9
1
5 7
1
9 ...

output:

1 1 1
1 6 5
1 2 4
1 5 6
1 2 4
1 1 1
1 1 1
1 5 6
1 2 4
1 4 2
1 1 1
1 1 1
-1 -1 -1
1 1 1
1 1 1
1 2 4
1 3 7
1 4 2
1 1 1
1 4 2
1 1 1
1 7 3
1 6 5
1 1 1
1 1 1
1 1 1
1 1 1
1 3 7
1 2 4
1 1 1
1 2 4
1 1 1
1 3 7
1 5 6
1 1 1
1 5 6
1 2 4
1 4 2
1 4 2
1 1 1
1 6 5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 2 4
1 7 3
1 4 2
1 3...

result:

ok 100 lines

Test #5:

score: -100
Wrong Answer
time: 828ms
memory: 28160kb

input:

100
2
100 100
87 49
2
38 68
61 81
2
41 26
82 40
2
15 92
26 90
2
87 50
76 15
2
41 85
57 30
2
52 7
73 19
2
78 15
95 71
2
51 72
5 34
2
20 83
74 1
2
63 42
74 75
2
97 96
35 72
2
17 84
98 52
2
84 37
50 5
2
55 26
62 4
2
67 13
45 64
2
11 93
45 58
2
39 9
64 26
2
49 17
40 18
2
38 51
34 2
2
30 6
50 60
2
19 24
...

output:

1 91 91
2 30 50
2 27 40
2 10 74
2 2 15
2 53 26
2 51 19
2 23 71
2 5 22
1 7 70
2 25 26
1 86 85
2 64 52
1 28 37
1 49 20
2 18 64
1 2 84
2 45 7
2 40 6
1 38 20
1 30 5
1 19 22
1 10 42
1 9 11
2 12 51
2 42 43
1 19 14
1 24 35
1 5 4
2 57 55
2 41 28
2 75 25
2 2 54
1 14 30
1 32 29
2 1 45
1 18 65
2 12 46
1 49 35
...

result:

wrong answer 5th lines differ - expected: '1 56 50', found: '2 2 15'
English 繁體中文 简体中文

Server Time: 2024-11-29 19:42:25 | OpenSource Project