QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214159#6550. Elimination Raceucup-team2112#TL 610ms9652kbC++175.8kb2023-10-14 17:36:182023-10-14 17:36:18

Judging History

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

  • [2023-10-14 17:36:18]
  • 评测
  • 测评结果:TL
  • 用时:610ms
  • 内存:9652kb
  • [2023-10-14 17:36:18]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(const pair<A, B> &p);
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p);
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A, class T = typename A::value_type> string to_string(const A &v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if (0) puts("No effect.")
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

/**
 * Author: Yuhao Yao
 * Date: 22-10-23
 * Description: Fast bipartite matching for \textbf{bipartite} graph $G = (L \cup R, E)$. Edges $E$ should be described as pairs such that pair $(x, y)$ means that there is an edge between the $x$-th vertex in $L$ and the $y$-th vertex in $R$. You can also get a vertex cover of a bipartite graph easily. 
 * Time: O(|E| \sqrt{|L| + |R|}).
 * Status: vertex cover correctness is tested on https://ac.nowcoder.com/acm/contest/885/F.
 */
struct Hopcroft {	
	int L, R; /// start-hash
	vi lm, rm; // record the matched vertex for each vertex on both sides.
	vi ldis, rdis; // put it here so you can get vertex cover easily.

	Hopcroft(int L, int R, const vector<pii> &es): L(L), R(R), lm(L, -1), rm(R, -1) {
		vector<vi> g(L);
		for (auto [x, y]: es) g[x].push_back(y);

		while (1) {
			ldis.assign(L, -1);
			rdis.assign(R, -1);
			bool ok = 0;
			vi que;
			rep(i, 0, L - 1) if (lm[i] == -1) {
				que.push_back(i);
				ldis[i] = 0;
			}
			rep(ind, 0, sz(que) - 1) {
				int i = que[ind];
				for (auto j: g[i]) if (rdis[j] == -1) {
					rdis[j] = ldis[i] + 1;
					if (rm[j] != -1) {
						ldis[rm[j]] = rdis[j] + 1;
						que.push_back(rm[j]);
					} else ok = 1;
				}
			}

			if (ok == 0) break;
			vi vis(R); // changing to static does not speed up.

			auto find = [&](auto &dfs, int i) -> int {
				for (auto j: g[i]) if (vis[j] == 0 && rdis[j] == ldis[i] + 1) {
					vis[j] = 1;
					if (rm[j] == -1 || dfs(dfs, rm[j])) {
						lm[i] = j;
						rm[j] = i;
						return 1;
					}
				}
				return 0;
			};
			rep(i, 0, L - 1) if (lm[i] == -1) find(find, i);
		}
	} /// end-hash
	
	vi getMatch() { return lm; } // returns lm.

	pair<vi, vi> vertex_cover() { /// start-hash
		vi lvc, rvc;
		rep(i, 0, L - 1) if (ldis[i] == -1) lvc.push_back(i);
		rep(j, 0, R - 1) if (rdis[j] != -1) rvc.push_back(j);
		return {lvc, rvc};
	} /// end-hash
};


int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	vector as(n - 1, vi(n));
	for (auto &vec : as) for (auto &x : vec) {
		cin >> x;
		x--;
	}
	auto Solve = [&](int s) -> void {
		vector<pii> es;
		vector<vector<int>> lsts(n - 1);
		rep(i, 0, n - 2) {
			auto &vec = as[i];
			int ind = find(all(vec), s) - vec.begin();
			rep(j, ind + 1, n - 1) {
				int v = vec[j];
				es.emplace_back(i, v);
			}
			lsts[i] = vector<int>(vec.begin() + ind + 1, vec.end());
		}
		auto lm = Hopcroft(n - 1, n, es).getMatch();
		if (count(all(lm), -1) > 0) {
			puts("No");
			return;
		} else {
			puts("Yes");
			vector<int> rm(n, -1);
			rep(i, 0, n - 2) rm[lm[i]] = i;
			vector<int> ords;
			vector<int> vis(n - 1);
			vector<int> used(n);
			vi sta;

			rep(i, 0, n - 2) if (vis[i] == 0) {
				auto dfs = [&](auto &dfs, int now) {
					vis[now] = 2;
					sta.push_back(now);
					while (1) {
						assert(sz(lsts[now]) > 0);
						int v = lsts[now].back();
						lsts[now].pop_back();
						if (used[v]) {
							continue;
						}
						int want = lm[now];
						if (want == v) {
							vis[now] = 1;
							used[v] = 1;
							sta.pop_back();
							ords.push_back(now);
							return;
						} else if (vis[rm[v]] == 2) {
							int u = rm[v];
							while (1) {
								int cur = sta.back();
								sta.pop_back();
								vis[cur] = 1;
								ords.push_back(cur);
								if (cur == u) break;
							}
							used[v] = 1;
							return;
						} else {
							assert(vis[rm[v]] == 0);
							dfs(dfs, rm[v]);
							if (vis[now] == 1) {
								used[v] = 1;
								return;
							}
						}
					}
				};
				dfs(dfs, i);
			}
			rep(i, 0, sz(ords) - 1) printf("%d%c", ords[i] + 1, " \n"[i == sz(ords) - 1]);
		}
	};
	rep(i, 0, n - 1) Solve(i);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

Yes
1 2 3
No
No
No

result:

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

Test #2:

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

input:

3
2 1 3
2 1 3

output:

No
Yes
2 1
No

result:

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

Test #3:

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

input:

2
1 2

output:

Yes
1
No

result:

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

Test #4:

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

input:

2
2 1

output:

No
Yes
1

result:

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

Test #5:

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

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
4 10 8 1 7 3 6 9 5 2
No
No
No
No
No
No
Yes
5 1 3 10 4 9 6 2 7 8
Yes
1 2 6 10 4 5 3 9 7 8
Yes
4 9 1 8 2 7 10 3 6 5
No

result:

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

Test #6:

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

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
9 6 8 2 1 7 5 3 4 10
No
No
Yes
10 3 6 4 9 5 8 1 2 7
No
No
Yes
2 5 8 1 4 10 3 9 7 6
No
Yes
10 8 1 2 4 9 6 7 3 5
No
No

result:

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

Test #7:

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

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 2 1 5 9 10 3 8 6 4
No
No
No
No
No
Yes
6 8 9 4 1 5 7 2 3 10
No
No
No
No

result:

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

Test #8:

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

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
10 4 2 9 3 8 1 5 6 7
No
No
No
No
No
No
Yes
7 1 8 5 4 10 2 3 6 9
Yes
3 8 4 1 5 6 10 9 2 7
No
No

result:

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

Test #9:

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

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
1 10 3 4 2 7 6 8 5 9
No
No
No
No
No
Yes
4 10 2 8 9 6 5 7 3 1
No
No
Yes
7 2 3 1 10 5 4 8 6 9
Yes
3 2 1 10 9 5 8 7 4 6

result:

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

Test #10:

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

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 6 5 8 10 9 4 3 7 2
No
Yes
10 7 2 5 6 1 4 9 3 8
No
Yes
1 2 7 5 6 3 4 8 9 10
No
No
No

result:

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

Test #11:

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

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
6 2 4 7 5 1 3 9 10 8
No
Yes
10 8 1 7 9 3 5 6 2 4
Yes
6 3 7 1 4 10 9 2 5 8
No
No
No
Yes
1 5 4 8 9 3 6 2 7 10
Yes
10 3 1 4 8 7 9 5 2 6
No
Yes
10 4 9 5 3 2 8 7 6 1

result:

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

Test #12:

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

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
9 6 3 4 7 8 10 5 1 2
No
Yes
9 7 4 5 1 10 6 8 2 3
Yes
2 1 4 9 3 6 7 8 5 10
Yes
9 6 4 8 10 5 7 3 1 2
No
No
No
No
No
No

result:

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

Test #13:

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

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
8 5 4 1 9 10 2 7 6 3
Yes
4 7 1 2 6 3 5 8 10 9
Yes
9 10 7 3 5 8 2 6 1 4
Yes
3 2 1 4 5 9 10 8 7 6
No
Yes
10 5 7 6 8 2 4 9 3 1
Yes
1 8 6 4 3 5 9 2 7 10
No
No
No
No

result:

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

Test #14:

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

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
8 5 4 1 7 9 6 2 10 3
Yes
8 6 2 5 1 7 4 10 3 9
Yes
1 8 5 3 2 4 6 9 7 10
No
Yes
4 2 5 7 6 1 3 10 9 8
No
Yes
8 10 3 9 1 7 6 5 4 2
No
No
No
No

result:

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

Test #15:

score: 0
Accepted
time: 604ms
memory: 9344kb

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
22 126 322 410 12 99 182 353 381 19 111 98 237 137 326 48 490 215 221 177 8 376 314 362 492 112 337 197 396 253 170 289 49 92 78 495 44 148 432 290 57 85 53 281 465 169 145 313 173 245 482 150 128 153 143 496 468 40 498 484 384 308 141 70 405 320 76 310 411 364 206 55 108 71 464 33 242 181 83 42...

result:

ok n=500, yes=171, no=329

Test #16:

score: 0
Accepted
time: 605ms
memory: 9284kb

input:

500
18 271 51 335 212 326 93 264 408 66 230 181 456 149 259 396 269 443 136 446 250 409 240 457 319 289 402 334 247 216 106 214 468 448 58 186 137 225 337 487 281 333 130 275 169 420 100 71 57 284 63 454 108 375 164 437 133 110 440 350 479 370 276 211 193 148 198 222 496 460 308 85 286 242 257 435 4...

output:

Yes
202 335 349 118 57 182 362 36 386 76 65 18 336 413 263 280 103 27 314 211 236 194 429 433 453 85 102 122 358 144 35 226 258 408 129 25 179 24 334 374 168 204 477 300 435 189 45 460 299 162 100 56 262 351 12 187 109 19 341 250 143 366 225 291 183 306 73 292 298 127 170 253 86 173 342 274 272 389 ...

result:

ok n=500, yes=185, no=315

Test #17:

score: 0
Accepted
time: 606ms
memory: 9216kb

input:

500
24 261 411 242 116 202 460 6 169 140 268 333 447 468 341 373 58 274 175 180 77 232 465 326 300 211 204 75 98 425 322 90 408 489 227 480 89 31 94 248 334 299 76 290 157 178 111 143 103 117 131 292 456 201 118 285 150 10 56 251 418 448 453 47 451 184 343 42 210 68 113 422 165 391 415 272 45 82 490...

output:

Yes
407 37 211 158 127 68 291 63 320 91 373 59 484 224 353 100 350 492 442 399 482 20 227 76 105 444 190 425 57 242 423 159 42 385 431 468 162 285 330 226 235 372 427 331 394 3 404 204 169 466 438 134 367 265 266 94 64 282 166 83 439 274 185 358 327 143 139 336 262 396 486 250 243 296 475 278 60 133...

result:

ok n=500, yes=186, no=314

Test #18:

score: 0
Accepted
time: 603ms
memory: 9416kb

input:

500
219 142 183 492 426 414 85 228 482 93 21 361 327 345 234 50 432 52 498 223 372 127 319 56 263 210 204 43 394 271 22 437 419 486 186 255 398 167 353 444 371 172 23 270 235 133 189 6 279 380 97 179 2 29 277 328 149 411 158 369 298 26 489 315 107 360 160 463 109 215 81 232 448 140 355 33 82 25 125 ...

output:

Yes
398 427 287 420 283 23 311 38 338 139 479 430 251 5 469 410 85 145 270 117 322 185 472 478 247 198 395 13 162 366 294 53 157 341 156 483 108 426 263 119 40 471 17 160 461 135 231 213 257 233 148 307 87 279 43 342 487 175 112 339 282 146 125 199 286 375 158 106 271 334 360 325 412 172 318 445 448...

result:

ok n=500, yes=188, no=312

Test #19:

score: 0
Accepted
time: 610ms
memory: 9652kb

input:

500
330 206 369 65 187 249 174 325 166 260 55 244 351 275 118 186 434 116 489 481 331 472 112 130 297 26 16 84 321 132 484 305 188 35 287 452 109 44 180 407 374 46 221 29 246 424 208 292 285 209 414 418 33 406 223 309 422 108 56 359 296 326 49 286 217 173 120 72 322 62 204 451 81 455 179 45 284 298 ...

output:

Yes
17 137 359 455 52 87 251 321 342 186 297 379 482 428 109 202 14 441 139 456 6 324 427 19 196 24 232 204 309 57 433 457 172 383 475 392 399 48 269 396 291 327 81 353 446 366 50 361 80 68 99 289 360 334 401 58 133 288 328 37 373 18 5 307 71 130 395 302 489 125 235 36 498 480 300 329 310 116 436 16...

result:

ok n=500, yes=175, no=325

Test #20:

score: 0
Accepted
time: 598ms
memory: 9544kb

input:

500
233 154 203 96 30 404 476 284 75 447 291 52 155 197 258 500 338 278 199 20 405 408 307 108 122 368 424 308 453 26 7 94 330 177 319 407 105 179 236 337 150 315 29 345 292 471 89 456 180 483 382 466 45 485 263 376 478 53 61 34 463 327 219 472 62 84 172 443 226 432 190 63 366 276 174 168 375 147 19...

output:

Yes
308 142 259 359 34 323 372 212 149 257 410 196 492 46 429 242 470 273 406 116 54 69 348 317 298 108 43 162 168 83 184 201 175 256 8 194 52 306 281 310 211 422 33 280 207 94 346 217 489 467 279 367 476 338 398 412 197 137 484 156 384 328 340 123 18 218 3 248 353 170 226 7 347 446 324 378 268 220 ...

result:

ok n=500, yes=182, no=318

Test #21:

score: 0
Accepted
time: 604ms
memory: 9360kb

input:

500
147 88 258 111 242 490 363 484 137 17 81 260 58 113 14 50 286 333 479 419 398 240 309 301 210 289 296 83 357 120 9 288 459 232 146 239 426 319 3 171 247 348 207 412 233 32 116 480 56 115 492 218 331 209 86 174 16 101 350 176 245 36 456 365 199 102 94 76 82 351 376 103 455 420 231 325 37 93 214 2...

output:

Yes
243 28 267 49 288 11 63 14 174 432 200 471 298 433 43 464 158 120 257 53 104 318 485 107 413 430 296 124 317 54 170 295 333 38 465 418 292 118 388 384 145 20 113 366 253 411 406 136 115 64 478 327 376 67 108 40 344 420 421 462 422 7 328 476 205 126 192 338 4 429 287 460 323 166 367 164 52 459 48...

result:

ok n=500, yes=180, no=320

Test #22:

score: 0
Accepted
time: 603ms
memory: 9352kb

input:

500
170 302 411 359 201 15 194 287 128 106 181 12 367 450 339 488 377 466 115 16 275 62 178 330 276 461 168 58 380 202 14 37 233 92 383 195 459 327 74 477 278 363 444 342 422 455 28 169 301 492 436 337 356 487 126 378 404 249 7 259 366 187 103 447 130 389 24 120 245 206 47 432 416 102 297 166 376 31...

output:

Yes
255 98 31 249 162 122 296 175 49 196 443 60 11 20 57 431 458 394 163 116 22 36 226 349 72 233 139 388 121 427 147 396 473 206 406 44 152 105 402 5 106 165 314 204 6 422 318 498 333 239 486 339 167 401 13 234 456 445 193 181 449 130 243 465 441 375 291 336 208 137 331 322 463 371 313 374 97 93 42...

result:

ok n=500, yes=174, no=326

Test #23:

score: 0
Accepted
time: 607ms
memory: 9108kb

input:

500
498 451 475 72 77 397 157 119 386 312 321 45 71 21 24 438 186 26 341 408 39 195 275 366 100 144 70 95 246 4 46 361 182 155 473 387 23 335 6 413 292 416 89 266 2 457 450 213 367 22 92 382 237 170 251 500 254 309 136 323 27 42 222 481 111 169 188 371 166 150 434 427 208 209 398 430 165 295 238 258...

output:

Yes
489 124 404 435 279 365 3 434 306 247 418 460 158 385 150 481 310 145 168 44 297 451 391 382 226 421 11 92 319 292 423 270 138 133 346 27 316 93 155 257 198 395 492 286 232 330 1 221 373 366 55 189 52 339 127 182 457 80 239 205 381 272 324 57 477 89 280 202 289 109 356 119 471 30 437 31 359 410 ...

result:

ok n=500, yes=187, no=313

Test #24:

score: 0
Accepted
time: 601ms
memory: 9300kb

input:

500
74 364 86 239 403 250 29 92 464 201 114 394 231 279 59 217 343 242 225 255 48 154 404 103 183 18 159 147 137 222 75 172 458 362 39 99 396 149 100 428 259 318 53 460 76 163 146 444 342 184 143 296 262 186 148 175 165 241 294 218 254 482 16 488 169 78 27 101 311 63 14 258 117 60 393 107 410 145 10...

output:

Yes
43 330 369 371 287 445 380 181 390 405 227 125 400 64 196 32 66 367 104 237 15 75 368 210 342 423 309 124 393 222 89 162 473 470 447 362 245 71 428 360 38 376 156 208 126 241 116 271 378 207 82 19 2 262 326 204 99 471 492 303 1 117 179 481 478 325 61 285 488 261 42 54 268 173 431 472 374 364 343...

result:

ok n=500, yes=177, no=323

Test #25:

score: -100
Time Limit Exceeded

input:

500
468 261 329 368 419 490 308 362 265 282 392 397 306 281 384 325 263 319 448 449 277 333 323 394 351 472 442 260 374 400 274 264 423 278 369 380 403 303 406 470 295 318 326 268 371 339 491 390 444 481 421 459 393 347 383 408 257 324 286 267 253 436 483 460 427 320 388 297 287 363 288 358 361 331 ...

output:

No
Yes
324 493 279 211 217 234 459 71 396 70 460 120 75 249 63 223 472 302 51 402 256 331 278 80 158 156 377 366 294 393 420 212 110 299 214 327 383 318 325 347 227 416 242 363 107 261 85 87 167 26 253 121 143 471 310 378 58 349 400 69 147 18 298 499 103 55 91 309 395 68 207 28 35 50 119 202 495 203...

result: