QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#113013	#6550. Elimination Race	eyiigjkn	TL	1ms	3612kb	C++14	1.5kb	2023-06-15 21:14:13	2023-06-15 21:14:16

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-15 21:14:16]
评测

测评结果：TL
用时：1ms
内存：3612kb

查看

[2023-06-15 21:14:13]
提交

answer

# include <bits/stdc++.h>
using namespace std;
int n,a[510][510],b[510][510],mch[1010],lst[510];
bitset<510> nvis,E[510];
bool dfs(int u)
{
	auto tmp=E[u-n]&nvis;
	for(int v=tmp._Find_first();v<=n;v=tmp._Find_next(v))
		if(nvis.test(v) && (!mch[v] || (nvis.reset(v),dfs(mch[v]))))
			return mch[u]=v,mch[v]=u,true;
	return false;
}
void slv(int x)
{
	for(int i=1;i<n;i++)
	{
		E[i].reset();
		for(int j=b[i][x]+1;j<=n;j++) E[i].set(a[i][j]);
	}
	for(int i=1;i<n;i++)
		if(nvis.set(),!dfs(i+n))
			return cout<<"No\n",fill(mch+1,mch+2*n,0),void();
	cout<<"Yes\n";
	static bool v1[510],v2[510];
	for(int i=1;i<n;i++) lst[i]=a[i][n];
	for(int i=1;i<n;i++)
	{
		int p=0;
		for(int j=1;j<n && !p;j++)
			if(mch[j+n]==lst[j]) p=j;
		if(p)
		{
			cout<<p<<" \n"[i==n-1];
			v1[p]=v2[lst[p]]=1;
			for(int j=1;j<n;j++)
			{
				int k=b[j][lst[j]];
				while(v2[a[j][k]]) k--;
				lst[j]=a[j][k];
			}
		}
		else
		{
			int p=1,u1,u2;
			static int nxt[510];
			for(int i=1;i<n;i++)
				if(!v1[i]) nxt[i]=mch[lst[i]]-n;
			for(p=1;v1[p];p++);
			u1=u2=p;
			do u1=nxt[u1],u2=nxt[nxt[u2]];while(u1!=u2);
			while(1)
			{
				mch[u1+n]=lst[u1];mch[lst[u1]]=u1+n;
				if((u1=nxt[u1])==u2) break;
			}
			i--;
		}
	}
	fill(mch+1,mch+2*n,0);
	fill(v1+1,v1+n,0);
	fill(v2+1,v2+n+1,0);
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j],b[i][a[i][j]]=j;
	for(int i=1;i<=n;i++) slv(i);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3556kb

input:

output:

Yes
2 1 3
No
No
No

result:

ok n=4, yes=1, no=3

Test #2:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

3
2 1 3
2 1 3

output:

No
Yes
1 2
No

result:

ok n=3, yes=1, no=2

Test #3:

score: 0

Accepted

time: 1ms

memory: 3556kb

input:

2
1 2

output:

Yes
1
No

result:

ok n=2, yes=1, no=1

Test #4:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

2
2 1

output:

No
Yes
1

result:

ok n=2, yes=1, no=1

Test #5:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

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

output:

Yes
7 9 1 4 6 8 10 3 5 2
No
No
No
No
No
No
Yes
5 1 8 2 4 7 3 6 9 10
Yes
1 2 5 6 7 8 9 3 4 10
Yes
3 4 5 6 7 10 1 2 9 8
No

result:

ok n=11, yes=4, no=7

Test #6:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

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

output:

Yes
7 10 4 1 2 6 9 8 3 5
No
No
Yes
5 7 10 1 8 9 6 2 3 4
No
No
Yes
2 3 5 1 6 7 9 4 8 10
No
Yes
2 10 4 1 3 5 8 9 7 6
No
No

result:

ok n=11, yes=4, no=7

Test #7:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

Yes
7 8 6 9 10 3 5 1 2 4
No
No
No
No
No
Yes
1 3 4 6 8 9 2 5 7 10
No
No
No
No

result:

ok n=11, yes=2, no=9

Test #8:

score: 0

Accepted

time: 1ms

memory: 3460kb

input:

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

output:

Yes
6 8 9 4 5 2 1 3 7 10
No
No
No
No
No
No
Yes
3 7 1 4 6 5 8 9 2 10
Yes
1 7 3 9 5 2 4 8 6 10
No
No

result:

ok n=11, yes=3, no=8

Test #9:

score: 0

Accepted

time: 1ms

memory: 3484kb

input:

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

output:

Yes
9 7 10 2 3 4 6 5 1 8
No
No
No
No
No
Yes
4 5 6 10 1 2 3 9 7 8
No
No
Yes
8 10 3 2 6 9 5 7 1 4
Yes
9 10 4 1 2 3 5 6 7 8

result:

ok n=11, yes=4, no=7

Test #10:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

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

output:

No
No
No
Yes
1 3 5 6 8 4 2 9 10 7
No
Yes
3 1 2 7 8 9 4 6 10 5
No
Yes
2 4 6 7 9 1 3 8 5 10
No
No
No

result:

ok n=11, yes=3, no=8

Test #11:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

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

output:

Yes
2 3 7 9 4 5 8 10 1 6
No
Yes
5 7 8 10 1 2 6 3 4 9
Yes
4 6 1 3 7 5 10 9 8 2
No
No
No
Yes
1 5 4 8 9 3 7 2 6 10
Yes
2 4 8 3 7 9 1 6 5 10
No
Yes
2 3 10 5 9 7 4 6 8 1

result:

ok n=11, yes=6, no=5

Test #12:

score: 0

Accepted

time: 0ms

memory: 3392kb

input:

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

output:

Yes
4 5 1 3 7 8 10 2 6 9
No
Yes
2 3 4 5 7 1 6 8 9 10
Yes
2 3 4 5 6 9 1 8 10 7
Yes
4 5 6 7 8 9 10 2 1 3
No
No
No
No
No
No

result:

ok n=11, yes=4, no=7

Test #13:

score: 0

Accepted

time: 1ms

memory: 3488kb

input:

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

output:

Yes
1 4 5 2 3 7 6 8 10 9
Yes
1 2 4 6 7 3 8 10 9 5
Yes
1 2 3 6 8 9 5 10 4 7
Yes
3 5 9 1 2 6 10 4 7 8
No
Yes
4 5 6 3 7 1 8 2 9 10
Yes
1 4 6 3 7 8 9 2 5 10
No
No
No
No

result:

ok n=11, yes=6, no=5

Test #14:

score: 0

Accepted

time: 1ms

memory: 3556kb

input:

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

output:

Yes
2 4 7 1 6 9 3 8 10 5
Yes
1 2 4 6 8 9 5 7 10 3
Yes
1 2 4 6 7 8 3 5 10 9
No
Yes
5 7 10 6 8 3 4 1 9 2
No
Yes
3 8 10 2 4 6 7 5 1 9
No
No
No
No

result:

ok n=11, yes=5, no=6

Test #15:

score: -100

Time Limit Exceeded

input:

500
446 156 267 294 482 398 430 13 311 318 474 426 140 484 83 387 257 136 69 305 295 283 287 55 52 65 322 249 43 56 331 443 226 214 341 182 389 464 84 477 187 40 327 411 248 10 223 165 379 293 12 9 5 230 309 367 2 397 265 59 361 118 196 316 390 213 194 167 483 452 114 345 263 219 87 94 160 224 200 2...

output:

Yes
124 171 342 8 53 267 275 319 433 2 6 16 33 38 65 71 73 86 97 102 139 151 153 155 170 191 200 247 260 281 287 332 350 370 371 394 408 412 469 471 492 498 499 3 17 35 59 80 87 88 90 129 143 145 150 196 259 261 273 279 289 292 306 308 309 321 336 345 355 380 389 409 410 416 419 421 425 438 52 163 5...