QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#33154#2223. Mad DiamondYaoBIGAC ✓145ms141576kbC++203.6kb2022-05-29 01:07:262022-05-29 01:07:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-29 01:07:28]
  • 评测
  • 测评结果:AC
  • 用时:145ms
  • 内存:141576kb
  • [2022-05-29 01:07:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18 + 7;

const int H = 20;
const int W = 360;
const int CW = 0;
const int CCW = 1;
const int DOWN = 2;
const int UP = 3;
vector<int> ins[W][H][W];
int nxt[W][H][W];
bool adj[H][W][4];
ll dp[W][H][W];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h;
	cin >> h;
	int w = 360;
	for (int y = 0; y < h; ++y) {
		int k;
		cin >> k;
		for (; k; --k) {
			int a, b;
			cin >> a >> b;

			for (int x = a; x != b; x = (x + 1) % w) {
				adj[y][x][CW] = 1;
				adj[y][(x + 1) % w][CCW] = 1;
			}
		}
		cin >> k;
		for (; k; --k) {
			int x;
			cin >> x;
			adj[y][x][DOWN] = 1;
			adj[y + 1][x][UP] = 1;
		}
	}

	for (int d = 0; d < w; ++d) {
		for (int y = 0; y < h; ++y) {
			for (int x = 0; x < w; ++x) {
				dp[d][y][x] = INF;
				if (x == d) {
					if (adj[y][x][DOWN]) nxt[d][y][x] = DOWN;
					else nxt[d][y][x] = -1;
				} else if (x == (d + w/2) % w) {
					if (adj[y][x][UP]) nxt[d][y][x] = UP;
					else nxt[d][y][x] = -1;
				} else {
					int diff = (x > d ? x - d : x + w - d);
					if (diff > w / 2) diff = diff - w;

					if (abs(diff) <= w / 8 && adj[y][x][DOWN]) {
						// Can change layer and angle <= 45 deg
						nxt[d][y][x] = DOWN;
					} else if (abs(diff) >= 3 * w / 8 && adj[y][x][UP]) {
						// Can change layer and angle <= 45 deg
						nxt[d][y][x] = UP;
					} else if (diff > 0 && adj[y][x][CCW]) {
						// Can go along layer counter-clockwise
						nxt[d][y][x] = CCW;
					} else if (diff < 0 && adj[y][x][CW]) {
						// Can go along layer clockwise
						nxt[d][y][x] = CW;
					} else if (abs(diff) < w / 4 && adj[y][x][DOWN]) {
						// Can change layer and angle < 90 deg
						nxt[d][y][x] = DOWN;
					} else if (abs(diff) > w / 4 && adj[y][x][UP]) {
						// Can change layer and angle < 90 deg
						nxt[d][y][x] = UP;
					} else {
						nxt[d][y][x] = -1;
					}
				}
				if (nxt[d][y][x] == DOWN) {
					ins[d][y + 1][x].push_back(UP);
				} else if (nxt[d][y][x] == UP) {
					ins[d][y - 1][x].push_back(DOWN);
				} else if (nxt[d][y][x] == CW) {
					ins[d][y][(x + 1) % w].push_back(CCW);
				} else if (nxt[d][y][x] == CCW) {
					ins[d][y][(x + w-1) % w].push_back(CW);
				}
			}
		}
	}

	int sy, sx, ty, tx;
	cin >> sy >> sx >> ty >> tx;

	vector<pair<int, pair<int, int>>> que, nxt_que;
	for (int d = 0; d < w; ++d) {
		if (nxt[d][ty][tx] == -1) {
			dp[d][ty][tx] = 0;
			que.emplace_back(d, make_pair(ty, tx));
		}
	}
	while(! que.empty()) {
		for (int qi = 0; qi < que.size(); ++qi) {
			int d = que[qi].first;
			int y = que[qi].second.first;
			int x = que[qi].second.second;
			for (int dir : ins[d][y][x]) {
				int ty = (dir == UP ? y - 1 : (dir == DOWN ? y + 1 : y));
				int tx = (dir == CW ? (x + 1) % w : (dir == CCW ? (x + w-1) % w : x));
				if (dp[d][ty][tx] > dp[d][y][x]) {
					dp[d][ty][tx] = dp[d][y][x];
					que.emplace_back(d, make_pair(ty, tx));
				}
			}
			if (dp[(d + 1) % w][y][x] > dp[d][y][x] + 1 && nxt[(d + 1) % w][y][x] == -1) {
				dp[(d + 1) % w][y][x] = dp[d][y][x] + 1;
				nxt_que.emplace_back((d + 1) % w, make_pair(y, x));
			}
			if (dp[(d + w-1) % w][y][x] > dp[d][y][x] + 1 && nxt[(d + w-1) % w][y][x] == -1) {
				dp[(d + w-1) % w][y][x] = dp[d][y][x] + 1;
				nxt_que.emplace_back((d + w-1) % w, make_pair(y, x));
			}
			// if (dp[d][y][x] <= 2) cerr << d << ' ' << y << ' ' << x << ": " << dp[d][y][x] << '\n';
		}

		que = nxt_que;
		nxt_que.clear();
	}

	if (dp[180][sy][sx] >= INF) {
		cout << "Impossible\n";
	} else {
		cout << dp[180][sy][sx] << '\n';
	}
}

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 76276kb

input:

2
2 10 170 190 350
4 15 140 195 345
2 320 40 130 220
0
0 191
0 90

output:

Impossible

result:

ok single line: 'Impossible'

Test #2:

score: 0
Accepted
time: 69ms
memory: 106564kb

input:

9
1 225 180
4 45 180 270 315
5 330 0 20 135 150 230 250 290 315 315
8 0 70 150 210 250 270 315 330
8 0 50 70 70 90 150 180 210 230 250 270 270 290 315 330 330
9 0 70 110 230 250 270 290 315 330
9 0 0 10 80 100 110 120 230 240 260 270 280 290 290 315 325 330 350
13 0 80 90 110 120 135 195 240 260 290...

output:

Impossible

result:

ok single line: 'Impossible'

Test #3:

score: 0
Accepted
time: 15ms
memory: 73328kb

input:

2
1 0 90
1 45
1 0 90
0
1 0
0 90

output:

Impossible

result:

ok single line: 'Impossible'

Test #4:

score: 0
Accepted
time: 28ms
memory: 73136kb

input:

2
1 0 90
1 47
1 0 90
0
1 0
1 90

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 34ms
memory: 76132kb

input:

2
2 10 170 190 350
4 15 165 195 345
2 320 40 130 220
0
0 191
1 132

output:

78

result:

ok single line: '78'

Test #6:

score: 0
Accepted
time: 24ms
memory: 79404kb

input:

3
1 180 0
1 180
1 90 0
1 0
2 90 180 270 0
0
1 0
1 0

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 20ms
memory: 78280kb

input:

3
1 180 0
1 180
1 90 270
2 270 0
2 90 180 270 0
0
0 0
2 0

output:

182

result:

ok single line: '182'

Test #8:

score: 0
Accepted
time: 19ms
memory: 77492kb

input:

3
1 0 180
2 0 180
1 90 180
2 270 90
2 90 180 270 0
0
0 0
2 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #9:

score: 0
Accepted
time: 23ms
memory: 78896kb

input:

3
1 180 0
1 180
2 180 270 0 90
2 270 0
2 90 180 270 0
0
1 0
1 0

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 32ms
memory: 83352kb

input:

4
0
2 0 180
1 270 180
2 270 90
2 90 135 180 45
1 135
2 45 180 225 0
0
3 0
3 0

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 36ms
memory: 81160kb

input:

4
0
2 0 180
1 90 270
3 270 0 90
3 45 90 135 225 315 0
3 225 270 0
2 45 180 225 0
0
3 0
3 0

output:

91

result:

ok single line: '91'

Test #12:

score: 0
Accepted
time: 39ms
memory: 82220kb

input:

4
1 0 180
2 0 180
1 0 90
3 270 0 180
1 45 270
2 315 0
2 45 180 225 0
0
0 0
3 0

output:

180

result:

ok single line: '180'

Test #13:

score: 0
Accepted
time: 38ms
memory: 85220kb

input:

4
1 0 180
1 180
1 270 180
2 90 180
2 45 90 135 0
1 45
2 45 180 225 0
0
0 0
3 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #14:

score: 0
Accepted
time: 44ms
memory: 88028kb

input:

5
1 180 0
1 180
2 90 180 270 0
2 0 180
2 90 315 0 45
5 270 0 90 135 180
4 22 112 203 225 248 292 315 0
4 203 315 112 157
2 22 180 203 0
0
2 0
4 0

output:

270

result:

ok single line: '270'

Test #15:

score: 0
Accepted
time: 34ms
memory: 87156kb

input:

5
1 180 0
1 180
2 90 180 270 0
2 0 180
3 45 180 225 270 315 0
7 225 270 315 0 45 90 180
4 22 45 90 112 157 225 292 315
6 248 292 337 67 90 135
2 22 180 203 0
0
2 0
4 0

output:

362

result:

ok single line: '362'

Test #16:

score: 0
Accepted
time: 39ms
memory: 85784kb

input:

5
0
2 0 180
1 90 270
3 270 0 90
3 90 135 225 315 0 45
6 225 315 0 45 135 180
5 45 90 112 157 203 225 248 292 315 337
5 292 22 67 112 180
2 22 180 203 0
0
2 0
4 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #17:

score: 0
Accepted
time: 51ms
memory: 88156kb

input:

5
1 180 0
1 180
2 180 270 0 90
3 270 0 180
2 90 180 315 45
5 225 270 315 45 135
4 135 157 180 225 248 315 337 112
2 225 135
2 22 180 203 0
0
2 0
3 2

output:

268

result:

ok single line: '268'

Test #18:

score: 0
Accepted
time: 47ms
memory: 88620kb

input:

6
0
2 0 180
2 180 270 0 90
3 270 90 180
2 45 135 270 0
7 225 270 0 45 90 135 180
5 90 112 135 180 203 248 292 337 0 22
7 203 248 270 315 22 67 180
4 22 157 225 248 270 315 337 0
3 203 337 157
2 22 180 203 0
0
4 0
1 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #19:

score: 0
Accepted
time: 47ms
memory: 89796kb

input:

6
0
2 0 180
1 180 90
2 270 90
2 90 225 270 0
4 225 0 45 180
3 45 157 180 203 225 337
9 248 315 0 22 45 67 112 157 180
3 203 225 270 292 337 22
6 203 270 315 45 90 135
2 22 180 203 0
0
4 0
1 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #20:

score: 0
Accepted
time: 35ms
memory: 90888kb

input:

6
1 180 0
1 180
1 90 0
2 270 90
2 270 315 0 135
6 225 315 0 90 135 180
4 67 90 135 157 203 225 248 337
11 203 248 292 337 0 22 45 67 112 157 180
4 45 67 90 112 135 157 203 248
6 270 315 0 22 112 180
2 22 180 203 0
0
2 4
2 4

output:

Impossible

result:

ok single line: 'Impossible'

Test #21:

score: 0
Accepted
time: 36ms
memory: 90080kb

input:

6
1 180 0
1 180
2 180 270 0 90
3 270 0 180
3 90 180 270 315 0 45
6 225 270 315 0 45 135
5 22 112 135 157 180 225 248 292 315 337
7 203 248 315 0 67 112 180
3 112 180 225 270 337 22
5 292 315 22 45 90
2 22 180 203 0
0
2 4
2 4

output:

Impossible

result:

ok single line: 'Impossible'

Test #22:

score: 0
Accepted
time: 49ms
memory: 95016kb

input:

7
1 0 180
1 180
2 180 270 0 90
3 270 0 90
2 90 225 270 0
6 225 270 0 45 90 180
5 22 67 112 157 225 248 270 292 337 0
8 203 248 292 315 22 90 112 157
3 157 225 248 270 337 67
12 203 225 248 270 292 315 337 45 67 90 112 135
8 33 56 67 78 101 112 123 146 157 203 225 237 303 337 348 22
8 214 259 281 292...

output:

Impossible

result:

ok single line: 'Impossible'

Test #23:

score: 0
Accepted
time: 38ms
memory: 95972kb

input:

7
1 0 180
1 180
1 270 90
3 270 90 180
3 135 180 225 315 0 90
4 315 0 135 180
4 45 135 180 270 292 315 0 22
6 270 337 0 45 112 157
5 22 45 67 112 135 180 203 292 315 0
10 270 292 315 337 22 45 67 90 135 180
7 33 45 90 101 112 146 168 259 303 326 337 348 0 22
7 259 281 326 0 56 78 157
2 11 180 192 0
0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #24:

score: 0
Accepted
time: 89ms
memory: 94244kb

input:

7
1 180 0
1 180
2 90 180 270 0
4 270 0 90 180
3 45 90 225 270 315 0
5 225 270 90 135 180
5 67 112 135 157 203 225 270 292 315 45
9 225 248 292 337 22 112 135 157 180
3 180 203 248 315 0 112
11 203 225 292 315 337 0 45 90 135 157 180
10 11 33 45 56 78 101 112 135 146 157 168 180 214 225 237 281 315 3...

output:

176

result:

ok single line: '176'

Test #25:

score: 0
Accepted
time: 38ms
memory: 96064kb

input:

7
1 0 180
1 180
1 90 270
3 270 0 90
2 135 180 225 45
3 45 90 180
2 67 135 157 22
6 225 315 22 45 135 157
5 45 67 90 135 180 203 225 248 0 22
12 225 248 270 292 315 337 22 67 112 135 157 180
9 22 56 67 78 101 112 135 146 157 168 192 225 248 281 292 303 315 11
7 237 292 56 67 90 123 180
2 11 180 192 0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #26:

score: 0
Accepted
time: 61ms
memory: 98924kb

input:

8
1 0 180
1 180
1 270 90
3 0 90 180
1 135 0
4 225 0 45 135
4 22 45 67 135 157 225 248 337
5 248 315 22 90 157
4 112 157 203 248 270 292 337 67
11 203 248 270 292 337 22 45 90 112 157 180
9 45 78 101 123 146 157 180 203 214 237 248 259 292 303 315 337 348 11
19 203 214 237 248 270 281 292 315 337 348...

output:

Impossible

result:

ok single line: 'Impossible'

Test #27:

score: 0
Accepted
time: 45ms
memory: 98888kb

input:

8
1 180 0
1 180
2 90 180 270 0
2 0 180
2 45 135 180 315
6 225 315 0 90 135 180
4 67 90 157 180 225 292 337 45
7 203 315 337 67 112 135 180
4 90 112 135 157 225 292 0 67
12 203 225 270 292 315 337 0 67 90 135 157 180
10 11 56 78 90 101 135 146 157 168 192 203 225 237 248 259 270 303 326 348 0
15 203 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #28:

score: 0
Accepted
time: 65ms
memory: 95660kb

input:

8
0
2 0 180
1 180 0
3 0 90 180
2 90 135 225 315
7 225 270 0 45 90 135 180
6 22 45 67 90 112 135 157 203 225 248 292 0
6 203 270 337 0 45 90
5 45 67 90 180 203 248 270 315 0 22
10 225 248 270 315 337 22 67 112 157 180
9 22 56 67 90 101 123 135 146 180 214 248 259 270 281 303 315 326 348
19 214 225 23...

output:

184

result:

ok single line: '184'

Test #29:

score: 0
Accepted
time: 80ms
memory: 98880kb

input:

8
0
2 0 180
1 180 90
1 180
2 90 135 225 45
5 225 0 90 135 180
5 22 90 135 157 180 203 225 270 292 337
8 203 225 270 315 337 67 112 135
3 135 180 270 292 337 112
8 203 248 270 0 90 112 157 180
8 22 56 78 90 112 135 146 157 180 192 203 248 259 270 281 11
14 192 237 259 292 11 33 56 67 78 101 112 135 1...

output:

183

result:

ok single line: '183'

Test #30:

score: 0
Accepted
time: 57ms
memory: 100092kb

input:

9
0
2 0 180
1 270 90
3 0 90 180
2 135 270 315 45
5 270 315 90 135 180
6 67 112 135 157 180 203 225 248 292 315 337 22
8 203 225 270 315 0 45 67 180
4 22 45 90 157 248 270 315 0
12 203 225 248 292 337 0 22 45 67 90 135 157
10 11 22 45 56 67 78 90 112 135 146 157 192 214 237 248 292 303 315 326 337
16...

output:

Impossible

result:

ok single line: 'Impossible'

Test #31:

score: 0
Accepted
time: 65ms
memory: 103292kb

input:

9
1 180 0
1 180
1 90 270
3 0 90 180
2 135 225 270 45
4 225 270 45 90
7 67 112 135 157 180 203 225 248 270 292 315 337 0 45
8 203 225 248 292 337 45 112 157
4 45 90 112 180 248 270 315 22
9 203 225 270 292 315 22 67 112 180
9 33 45 56 67 78 112 123 168 192 214 225 248 270 281 292 315 337 11
15 192 21...

output:

Impossible

result:

ok single line: 'Impossible'

Test #32:

score: 0
Accepted
time: 71ms
memory: 101664kb

input:

9
1 0 180
1 180
1 180 0
3 270 90 180
3 135 180 270 315 0 90
5 225 315 0 135 180
5 45 135 157 180 225 270 292 315 337 22
8 203 225 270 315 337 90 135 157
4 90 112 180 203 248 292 337 67
10 225 248 292 315 45 67 112 135 157 180
10 33 45 56 90 101 123 146 168 180 192 203 225 248 259 270 281 303 348 0 2...

output:

Impossible

result:

ok single line: 'Impossible'

Test #33:

score: 0
Accepted
time: 75ms
memory: 101756kb

input:

9
1 180 0
1 180
2 180 270 0 90
3 270 0 180
1 315 135
6 225 270 315 90 135 180
5 67 112 157 203 225 248 270 292 337 45
6 225 270 315 337 45 112
4 45 90 112 157 180 225 248 270
12 225 248 292 315 337 0 22 45 90 112 157 180
10 22 45 56 78 90 101 112 123 146 192 203 214 237 259 281 303 315 326 348 11
15...

output:

Impossible

result:

ok single line: 'Impossible'

Test #34:

score: 0
Accepted
time: 57ms
memory: 105012kb

input:

10
1 0 180
1 180
2 90 180 270 0
3 270 90 180
2 180 270 315 90
6 225 270 315 45 135 180
4 22 45 67 157 270 292 337 0
10 203 225 248 292 315 0 67 90 157 180
3 248 270 315 337 0 67
11 203 248 270 292 337 0 45 90 112 135 157
6 22 56 78 101 123 135 146 248 281 303 348 0
16 225 259 270 281 315 326 337 348...

output:

Impossible

result:

ok single line: 'Impossible'

Test #35:

score: 0
Accepted
time: 59ms
memory: 104584kb

input:

10
0
2 0 180
1 0 270
2 0 180
2 45 135 270 315
7 225 270 315 0 45 135 180
5 22 67 112 135 157 203 225 270 315 0
5 203 292 0 45 90
4 45 67 90 180 225 315 0 22
8 203 248 315 337 22 67 112 180
8 22 56 67 123 135 157 168 192 203 259 270 303 315 348 0 11
15 203 259 281 303 315 348 0 33 45 67 123 135 157 1...

output:

Impossible

result:

ok single line: 'Impossible'

Test #36:

score: 0
Accepted
time: 77ms
memory: 107084kb

input:

10
1 0 180
1 180
1 90 0
2 270 90
2 225 270 0 135
4 315 0 90 180
3 22 67 112 157 180 337
7 225 270 337 0 22 112 180
4 22 45 67 180 270 292 315 337
10 203 225 248 270 292 337 0 45 67 180
9 33 45 56 78 90 168 180 192 225 237 259 270 292 315 337 348 0 22
14 203 214 225 237 248 281 292 326 348 22 45 78 9...

output:

Impossible

result:

ok single line: 'Impossible'

Test #37:

score: 0
Accepted
time: 67ms
memory: 106588kb

input:

10
1 0 180
1 180
1 180 0
3 0 90 180
2 45 225 270 315
5 270 315 0 45 135
3 67 112 157 270 292 337
7 270 0 22 45 67 112 157
3 112 180 203 248 292 0
9 203 270 292 315 22 45 90 135 180
6 33 123 168 203 214 259 281 292 326 348 0 22
12 214 270 303 315 326 348 22 78 112 135 146 157
8 22 67 90 112 123 146 1...

output:

Impossible

result:

ok single line: 'Impossible'

Test #38:

score: 0
Accepted
time: 74ms
memory: 110176kb

input:

11
1 180 0
2 0 180
1 90 180
2 270 0
2 225 270 315 180
4 225 270 315 180
2 180 225 337 157
8 203 248 270 292 315 337 135 157
4 157 180 225 248 270 292 337 90
8 248 292 315 337 90 112 157 180
8 11 67 78 90 101 146 168 248 259 270 281 292 303 326 337 348
13 225 248 259 281 0 22 56 67 78 101 123 146 157...

output:

254

result:

ok single line: '254'

Test #39:

score: 0
Accepted
time: 96ms
memory: 112332kb

input:

11
1 180 0
1 180
1 0 270
2 270 0
3 90 180 225 270 315 0
6 270 315 0 45 90 180
5 67 90 112 157 203 248 270 292 337 22
11 203 248 292 315 337 22 45 67 112 157 180
3 90 135 180 203 248 292
7 225 315 337 0 45 90 157
4 112 123 135 315 326 348 0 101
6 248 0 101 123 135 157
4 101 112 168 214 225 237 259 78...

output:

Impossible

result:

ok single line: 'Impossible'

Test #40:

score: 0
Accepted
time: 74ms
memory: 109420kb

input:

11
0
2 0 180
1 0 270
1 0
1 45 315
5 225 270 315 0 45
3 22 45 67 203 315 337
7 203 225 248 292 0 67 180
3 67 90 112 157 248 45
10 203 225 248 270 315 0 45 67 112 157
11 11 33 56 67 78 112 123 135 146 157 168 214 237 259 270 281 292 303 326 337 348 0
15 225 237 270 292 315 326 348 22 45 56 78 112 123 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #41:

score: 0
Accepted
time: 80ms
memory: 108052kb

input:

11
1 180 0
2 0 180
1 0 90
2 270 180
2 45 180 270 0
6 225 270 315 0 90 180
6 67 90 112 135 157 180 225 270 315 337 0 45
8 203 248 292 337 45 90 135 180
6 45 67 90 112 135 180 203 225 270 315 0 22
10 225 248 270 315 337 0 45 90 112 180
8 22 56 67 101 112 168 180 225 259 270 281 303 326 337 0 11
14 225...

output:

546

result:

ok single line: '546'

Test #42:

score: 0
Accepted
time: 35ms
memory: 82712kb

input:

4
0
2 0 180
1 0 270
2 270 0
3 45 180 225 270 315 0
2 225 90
2 45 180 225 0
0
0 0
2 0

output:

180

result:

ok single line: '180'

Test #43:

score: 0
Accepted
time: 115ms
memory: 122764kb

input:

15
1 180 0
1 180
1 270 180
2 270 0
3 135 180 225 270 315 90
4 0 45 90 135
6 22 67 112 135 157 180 203 225 248 270 337 0
12 203 225 248 270 292 315 337 0 45 90 135 157
5 22 45 67 90 112 135 157 180 270 292
9 225 248 315 0 45 67 112 135 157
9 22 33 45 56 78 90 123 135 157 214 248 259 270 281 315 337 0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #44:

score: 0
Accepted
time: 63ms
memory: 123392kb

input:

15
0
2 0 180
1 0 270
2 270 90
2 135 225 270 0
6 225 315 45 90 135 180
5 112 135 180 203 225 270 292 315 337 67
8 225 270 292 45 67 90 157 180
4 90 157 203 225 292 337 0 22
11 225 248 270 315 337 22 45 67 90 157 180
8 11 33 56 67 78 101 112 146 168 214 237 259 270 303 337 0
15 214 248 270 303 315 326...

output:

Impossible

result:

ok single line: 'Impossible'

Test #45:

score: 0
Accepted
time: 90ms
memory: 120860kb

input:

15
1 180 0
2 0 180
1 270 90
2 270 180
2 45 135 225 315
3 315 0 45
4 22 135 157 248 270 292 315 0
9 203 248 292 337 22 67 112 135 157
4 67 90 180 203 225 292 337 45
3 292 315 337
8 33 45 78 135 146 168 180 192 225 237 248 259 270 281 326 337
23 192 203 214 237 259 281 292 303 315 326 348 0 11 22 33 5...

output:

Impossible

result:

ok single line: 'Impossible'

Test #46:

score: 0
Accepted
time: 86ms
memory: 124952kb

input:

15
1 180 0
1 180
2 90 180 270 0
2 0 180
3 90 135 180 270 315 45
4 270 315 45 135
4 112 135 180 248 270 315 337 90
7 248 292 337 22 112 157 180
3 67 203 270 315 0 45
7 203 225 315 22 67 135 157
7 56 78 90 123 135 146 157 180 225 270 281 303 337 33
17 192 214 225 281 303 315 326 337 11 33 45 67 90 112...

output:

Impossible

result:

ok single line: 'Impossible'

Test #47:

score: 0
Accepted
time: 124ms
memory: 124956kb

input:

15
1 180 0
1 180
1 270 180
2 270 90
3 45 90 135 180 225 315
6 270 315 0 45 135 180
5 45 112 135 157 180 225 248 270 337 0
9 270 292 315 337 0 22 45 90 135
4 22 67 90 157 180 248 292 337
7 248 270 292 315 337 112 180
8 22 56 67 90 101 203 214 237 259 270 281 292 326 337 348 11
16 192 203 214 270 292 ...

output:

387

result:

ok single line: '387'

Test #48:

score: 0
Accepted
time: 145ms
memory: 137268kb

input:

20
0
2 0 180
1 180 0
2 0 90
2 225 270 0 180
4 270 315 90 135
4 22 45 90 112 157 292 337 0
7 225 292 315 337 22 67 135
3 90 157 203 270 292 67
9 225 292 315 337 45 67 112 157 180
9 11 22 33 56 67 90 123 135 168 180 214 259 270 281 303 326 337 0
18 192 203 225 248 270 292 315 337 348 22 33 67 101 123 ...

output:

764

result:

ok single line: '764'

Test #49:

score: 0
Accepted
time: 119ms
memory: 141576kb

input:

20
1 0 180
1 180
2 90 180 270 0
2 0 180
1 180 45
5 225 45 90 135 180
4 22 112 157 180 225 248 270 0
5 203 270 22 135 180
3 67 157 225 337 0 22
8 203 225 292 337 0 45 157 180
8 33 146 157 168 192 225 237 270 292 303 315 326 337 348 0 22
15 225 237 259 270 281 303 326 348 0 22 45 112 146 168 180
7 22 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #50:

score: 0
Accepted
time: 105ms
memory: 136420kb

input:

20
1 180 0
2 0 180
1 90 270
2 90 180
2 135 270 315 45
2 270 315
3 67 157 225 270 315 45
10 203 248 292 315 22 67 90 112 157 180
2 22 45 135 0
1 225
9 11 56 67 123 135 146 157 168 225 248 281 292 303 315 326 337 348 0
20 192 203 214 237 259 270 281 303 326 348 11 22 33 45 90 112 123 146 168 180
8 45 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #51:

score: 0
Accepted
time: 108ms
memory: 139696kb

input:

20
1 180 0
1 180
1 0 180
2 270 0
3 90 180 270 315 0 45
4 225 315 0 90
2 22 225 248 0
5 203 292 337 112 135
5 22 45 67 112 203 225 270 315 337 0
9 225 248 270 292 22 45 90 157 180
10 45 67 78 90 101 123 135 146 157 180 225 237 248 270 292 303 315 326 337 22
16 192 203 214 225 270 281 326 348 11 22 33...

output:

Impossible

result:

ok single line: 'Impossible'

Test #52:

score: 0
Accepted
time: 112ms
memory: 138384kb

input:

20
1 180 0
1 180
1 0 180
3 270 0 180
2 135 180 225 90
3 270 315 180
3 67 135 270 292 337 45
10 203 225 248 270 337 0 22 45 135 157
4 45 67 90 157 203 225 292 337
11 203 248 270 292 315 337 45 67 112 135 180
9 45 56 90 112 123 146 168 180 203 225 248 259 292 303 315 326 0 33
17 192 214 237 259 270 28...

output:

Impossible

result:

ok single line: 'Impossible'