QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#22493	#2353. Maharajas are Going Home	DaBenZhongXiaSongKuaiDi	AC ✓	853ms	28308kb	C++20	2.8kb	2022-03-09 19:09:28	2022-04-30 01:12:44

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:12:44]
评测

测评结果：AC
用时：853ms
内存：28308kb

查看

[2022-03-09 19:09:28]
提交

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;
	int zsth,zx,zy;
	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;
		zx=1000000000;
		zy=1000000000;
		for(sth=1;sth<=k;sth++)
		{
		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;
				}
			}
		}
		if(ansx==tx[sth]&&ansy==ty[sth])continue;
		if(ansx<zx||(ansx==zx&&ansy<zy))
		{
			zsth=sth;
			zx=ansx;
			zy=ansy;
		}
		break;
		}
		printf("%d %d %d\n",zsth,zx,zy);
	}
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 848ms

memory: 28308kb

input:

output:

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

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 838ms

memory: 28248kb

input:

1
1
1 1

output:

-1 -1 -1

result:

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

Test #3:

score: 0

Accepted

time: 839ms

memory: 28268kb

input:

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 853ms

memory: 28156kb

input:

output:

result:

ok 100 lines

Test #5:

score: 0

Accepted

time: 835ms

memory: 28148kb

input:

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 780ms

memory: 28240kb

input:

output:

result:

ok 100 lines

Test #7:

score: 0

Accepted

time: 784ms

memory: 28240kb

input:

output:

result:

ok 100 lines

Test #8:

score: 0

Accepted

time: 782ms

memory: 28248kb

input:

output:

result:

ok 100 lines

Test #9:

score: 0

Accepted

time: 824ms

memory: 28188kb

input:

output:

1 1000 2000
2 293 1537
2 1956 1638
6 411 778
1 82 549
1 1312 528
4 776 700
1 115 17
9 1021 283
9 411 1800
1 236 1082
1 849 1864
1 627 1550
1 679 605
9 1531 716
2 1734 493
9 1032 1455
4 484 204
1 464 607
3 899 541
1 126 1350
1 256 681
4 500 1909
1 265 627
2 510 763
1 198 831
1 507 263
5 153 1879
1 38...

result:

ok 100 lines

Test #10:

score: 0

Accepted

time: 842ms

memory: 28184kb

input:

output:

1 44 1482
5 68 1990
7 1217 1339
1 414 64
7 291 622
8 67 650
4 258 1850
2 804 1828
2 503 381
7 633 975
2 254 37
1 78 364
1 604 1887
4 723 391
3 1772 1492
2 544 145
9 1062 881
4 389 1990
3 29 469
1 265 1897
1 1018 940
2 77 75
5 336 223
1 426 1033
3 982 1837
1 199 1844
1 875 1529
3 405 695
1 960 524
1 ...

result:

ok 100 lines

Test #11:

score: 0

Accepted

time: 807ms

memory: 28228kb

input:

output:

7 572 28
6 383 1743
9 599 1466
2 1958 866
-1 -1 -1
1 1386 308
-1 -1 -1
3 400 1757
1 197 670
-1 -1 -1
1 724 1363
-1 -1 -1
4 557 877
3 313 145
2 1510 1739
1 1075 845
-1 -1 -1
4 804 746
3 223 1962
1 434 382
7 1493 365
2 1884 321
7 734 1584
2 117 1461
-1 -1 -1
1 59 349
4 242 229
1 226 1352
7 27 1838
1 1...

result:

ok 100 lines

Test #12:

score: 0

Accepted

time: 815ms

memory: 28260kb

input:

output:

-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
1 551 1880
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
1 47 992
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-...

result:

ok 100 lines

Test #13:

score: 0

Accepted

time: 778ms

memory: 28240kb

input:

output:

-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 ...

result:

ok 100 lines