QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54303#2223. Mad DiamondKING_UT#AC ✓5ms14300kbC++202.6kb2022-10-07 19:59:392022-10-07 19:59:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 19:59:41]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:14300kb
  • [2022-10-07 19:59:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll
using uint=unsigned;
using ull=unsigned ll;

#define gnr(i,a,b)for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define rng(i, a, b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) rng(i,0,n)
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
using vi=vc<int>;
#define a first
#define b second
#define mp make_pair
using vi=vc<int>;
#define pb push_back
#define eb emplace_back
template<class t,class u>bool chmax(t &a,u b){
	if(a <b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmin(t &a,u b){
	if(a>b){a=b;return true;}
	else return false;
}

#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>void mkuni(vc<t>&vs){
	sort(all(vs));
	vs.erase(unique(all(vs)),vs.ed);
}
template<class t>int lwb(const vc<t>&vs,t a){
	return lower_bound(all(vs),a)-vs.bg;
}

bool inc(int a,int b,int c){return a<=b&&b<=c;}

const int inf=INT_MAX/2-100;

using pi=pair<int,int>;

const int nmax=21;
const int L=360;
bool go[nmax][L][4];
int dist[nmax][L][L];

void slv(){
	int n;cin>>n;
	rep(i,n){
		{
			int k;cin>>k;
			rep(_,k){
				int x,y;cin>>x>>y;
				x%=L;
				y%=L;
				while(x!=y){
					int z=(x+1)%L;
					go[i][x][2]=true;
					go[i][z][3]=true;
					x=z;
				}
			}
		}
		{
			int k;cin>>k;
			rep(_,k){
				int x;cin>>x;
				x%=L;
				go[i][x][0]=true;
				go[i+1][x][1]=true;
			}
		}
	}
	n++;
	
	rep(i,n)rep(j,L)rep(k,L)dist[i][j][k]=inf;
	
	using Q=tuple<int,int,int,int>;
	deque<Q> q;
	auto reach=[&](int i,int j,int k,int d,bool f){
		if(chmin(dist[i][j][k],d)){
			if(f)q.push_front(Q(i,j,k,d));
			else q.pb(Q(i,j,k,d));
		}
	};
	{
		int i,j;cin>>i>>j;j%=L;
		reach(i,j,0,0,true);
	}
	auto vert=[&](int x){
		return abs(x%L-180);
	};
	int tari,tarj;cin>>tari>>tarj;tarj%=L;
	int ans=inf;
	while(si(q)){
		auto [i,j,k,d]=q.front();q.pop_front();
		if(dist[i][j][k]!=d)continue;
		pi nx(90,-1);
		if(go[i][j][0])chmin(nx,pi(vert(j+k),0));
		if(go[i][j][1])chmin(nx,pi(vert(j+k+180),1));
		if(go[i][j][2])chmin(nx,pi(vert(j+k+90),2));
		if(go[i][j][3])chmin(nx,pi(vert(j+k+270),3));
		if(nx.b==-1){
			//still
			if(i==tari&&j==tarj){
				chmin(ans,d);
			}
			reach(i,j,(k+1)%L,d+1,false);
			reach(i,j,(k+L-1)%L,d+1,false);
		}
		else if(nx.b==0)reach(i+1,j,k,d,true);
		else if(nx.b==1)reach(i-1,j,k,d,true);
		else if(nx.b==2)reach(i,(j+1)%L,k,d,true);
		else if(nx.b==3)reach(i,(j+L-1)%L,k,d,true);
	}
	if(ans>=inf)cout<<"Impossible"<<endl;
	else cout<<ans<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	slv();
}

詳細信息

Test #1:

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

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: 4ms
memory: 9872kb

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: 3ms
memory: 6752kb

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: 0ms
memory: 8052kb

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: 3ms
memory: 6440kb

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: 2ms
memory: 7136kb

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: 3ms
memory: 7364kb

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: 3ms
memory: 6800kb

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: 1ms
memory: 7356kb

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: 3ms
memory: 7332kb

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: 0ms
memory: 7352kb

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: 3ms
memory: 7500kb

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: 3ms
memory: 6392kb

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: 3ms
memory: 7264kb

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: 0ms
memory: 8288kb

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: 0ms
memory: 7636kb

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: 3ms
memory: 7672kb

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: 3ms
memory: 9116kb

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: 2ms
memory: 8652kb

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: 0ms
memory: 8120kb

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: 4ms
memory: 8712kb

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: 3ms
memory: 7612kb

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: 3ms
memory: 8308kb

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: 3ms
memory: 8516kb

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: 3ms
memory: 7896kb

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: 3ms
memory: 9080kb

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: 3ms
memory: 8496kb

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: 3ms
memory: 8696kb

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: 2ms
memory: 8792kb

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: 2ms
memory: 10388kb

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: 0ms
memory: 10548kb

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: 2ms
memory: 10692kb

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: 2ms
memory: 10448kb

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: 2ms
memory: 9572kb

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: 4ms
memory: 9804kb

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: 1ms
memory: 9924kb

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: 2ms
memory: 9592kb

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: 2ms
memory: 10088kb

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: 4ms
memory: 11660kb

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: 4ms
memory: 11436kb

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: 3ms
memory: 10496kb

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: 3ms
memory: 6584kb

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: 4ms
memory: 12760kb

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: 0ms
memory: 13500kb

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: 4ms
memory: 13468kb

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: 4ms
memory: 12952kb

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: 4ms
memory: 12668kb

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: 2ms
memory: 14224kb

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: 5ms
memory: 14300kb

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: 2ms
memory: 14284kb

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: 4ms
memory: 14228kb

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: 1ms
memory: 14224kb

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'