QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373029#5276. K-Shaped Figureskevinyang#TL 325ms4504kbC++175.9kb2024-03-31 23:42:172024-03-31 23:42:46

Judging History

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

  • [2024-03-31 23:42:46]
  • 评测
  • 测评结果:TL
  • 用时:325ms
  • 内存:4504kb
  • [2024-03-31 23:42:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<int> P;

P fix(P a){
	if(a.y < 0 || (a.y == 0 && a.x < 0)){
		a = a*-1;
	}
	return a;
}

template<class T>
T polygonArea2(vector<Point<T>>& v) {
	T a = v.back().cross(v[0]);
	rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]);
	return a;
}

template<class P> bool onSegment(P s, P e, P p) {
	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

string f(int a){
	string s = to_string(a/2);
	s.push_back('.');
	if(a%2==1)s.push_back('5');
	else s.push_back('0');
	return s;
}

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		if(n==0)return 0;
		map<P,int>hm;
		int m = 0;
		vector<pair<int,int>>a(n);
		vector<P>arr;
		
		for(int i = 0; i<n; i++){
			int x,y;
			cin >> x >> y;
			P p{x,y};
			cin >> x >> y;
			P p2{x,y};
			int u = 0; int v = 0;
			if(!hm.count(p)){
				hm[p] = m;
				m++;
				arr.push_back(p);
			}
			if(!hm.count(p2)){
				hm[p2] = m;
				m++;
				arr.push_back(p2);
			}
			u = hm[p];
			v = hm[p2];
			a[i] = {u,v};
		}
		vector<int>have(m*m);
		assert(arr.size()==m);
		vector<vector<int>>adj(m);
		vector<int>hid(m);
		for(int i = 0; i<n; i++){
			int u = a[i].first;
			int v = a[i].second;
			adj[u].push_back(v);
			adj[v].push_back(u);
			//cout << u << ' ' << v << '\n';
		}
		sort(arr.begin(),arr.end(), [](P a, P b){
			return P{a.x,-a.y} < P{b.x,-b.y};
		});
		vector<pair<int,int>>vals;
		vector<int>idx(m);
		for(int i = 0; i<m; i++){
			hid[hm[arr[i]]] = i;
		}
		for(int i = 0; i<m; i++){
			idx[i] = i;
		}
		for(int i = 0; i<n; i++){
			int u = hid[a[i].first];
			int v = hid[a[i].second];
			have[u*m+v]++;
			have[v*m+u]++;
		}
		for(int i = 0; i<m; i++){
			for(int j = i+1; j<m; j++){
				vals.push_back({i,j});
			}
		}
		sort(vals.begin(),vals.end(), [&](pair<int,int>a, pair<int,int> b){
			P vec1 = (arr[a.first]-arr[a.second]).perp();
			P vec2 = (arr[b.first]-arr[b.second]).perp();
			vec1 = fix(vec1);
			vec2 = fix(vec2);
			if(vec1.cross(vec2)!=0)
				return vec1.cross(vec2) > 0;
			return make_pair(a.second,a.first) < make_pair(b.second,b.first);
		});
		int ans = 0;
		for(auto [c,d] : vals){
			int x = idx[c];
			int y = idx[d];
			
			int l = min(x,y);
			int r = max(x,y);
			//cout << l << ' ' << r << '\n';
			/*
			cout << c << ' ' << d << '\n';
			cout << arr[l] << ' ' << arr[r] << '\n';
			for(int i = 0; i<m; i++){
				cout << arr[i] << ' ';
			}
			cout << '\n';
			*/
			if(have[c*m+d]){
				int mul = have[c*m+d];
				vector<bool>bad(m);
				for(int i = 0; i<m; i++){
					if(i==l || i==r)bad[i] = true;
					else if(arr[i].cross(arr[l],arr[r]) == 0){
						bad[i] = true;
					}
				}
				for(int i = 0; i<m; i++){
					if(i==l || i==r)continue;
					//
					if(onSegment(arr[l],arr[r],arr[i])){
						//cout << arr[l] << ' ' << arr[r] << ' ' << arr[i] << '\n';
						int u = hm[arr[i]];
						int cl = 0;
						int cr = 0;
						vector<P>lt;
						vector<P>rt;
						for(int nxt: adj[u]){
							int id = idx[hid[nxt]];
							if(bad[id])continue;
							if(id < l){
								cl++;
								lt.push_back(arr[id]-arr[i]);
							}
							else{
								if(id < r){
									//cout << id << ' ' << l << ' ' << r << '\n';
									//cout << arr[id] << ' ' << arr[l] << ' ' << arr[r] << '\n';
								}
								assert(id > r);
								cr++;
								rt.push_back(arr[id]-arr[i]);
							}
						}
						sort(lt.begin(),lt.end(),[](P a, P b){
							return a.cross(b) > 0;
						});
						sort(rt.begin(),rt.end(),[](P a, P b){
							return a.cross(b) > 0;
						});
						if(true){
							int cnt = 0;
							for(int i = 1; i<lt.size(); i++){
								if(lt[i-1].cross(lt[i])==0){
									cnt++;
									ans-=cnt*mul;
								}
								else{
									cnt = 0;
								}
							}
						}
						if(true){
							int cnt = 0;
							for(int i = 1; i<rt.size(); i++){
								if(rt[i-1].cross(rt[i])==0){
									cnt++;
									ans-=cnt*mul;
								}
								else{
									cnt = 0;
								}
							}
						}
						//cout << cl << ' ' << cr << '\n';
						ans+=cl*(cl-1)/2 * mul;
						ans+=cr*(cr-1)/2 * mul;
					}
				}
				//cout << arr[l] << ' ' << arr[r] << '\n';
			}
			
			swap(idx[c],idx[d]);
			swap(arr[x],arr[y]);
		}
		cout << ans << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
5
0 0 0 10
0 5 3 10
0 5 3 0
0 5 7 4
0 5 6 2
8
0 0 10 10
3 4 4 4
4 4 4 5
3 4 4 4
7 7 7 8
7 7 8 7
5 5 4 6
5 5 3 7

output:

6
2

result:

ok 2 number(s): "6 2"

Test #2:

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

input:

10
3
-1 -1 0 -1
-1 -1 0 -1
-1 -1 1 1
3
1 -1 0 0
0 -1 1 1
0 1 1 -1
3
0 -1 1 1
-1 1 1 -1
1 1 -1 0
3
-1 0 0 1
-1 1 0 1
-1 1 -1 0
3
-1 1 1 1
1 0 0 -1
1 -1 -1 0
3
0 -1 0 0
1 -1 0 0
-1 -1 1 1
3
1 0 1 1
1 -1 1 0
0 -1 -1 0
3
1 1 0 -1
-1 0 0 1
0 1 -1 0
3
1 0 0 -1
1 0 1 -1
1 0 0 0
3
-1 -1 -1 0
1 -1 1 0
1 0 0 -1

output:

0
0
0
0
0
1
0
0
0
0

result:

ok 10 numbers

Test #3:

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

input:

10
3
-3 2 -2 -1
3 -2 3 -4
3 4 2 5
3
0 -1 5 2
-4 -2 -1 5
1 4 5 -4
3
-3 5 -5 -5
-5 -4 -1 -3
-1 -5 -5 -1
3
-3 3 3 5
1 5 -4 5
2 -5 4 -5
3
4 2 -4 1
1 -5 1 4
-3 5 0 -3
3
3 -3 4 -2
-4 0 -5 -2
-5 2 -1 -4
3
4 -3 2 5
-3 -5 1 -4
5 2 0 5
3
-5 4 -4 -2
-5 -2 -5 2
2 4 -2 -5
3
2 -2 -4 0
2 4 0 -5
-4 -3 0 -4
3
2 5 1 ...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

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

input:

10
3
17 -61 16 46
-77 4 48 29
-83 -85 64 -98
3
8 87 72 94
-48 72 -53 -78
-55 95 76 6
3
58 -2 -20 -59
57 20 -50 -7
24 -51 -87 38
3
-20 43 38 73
-13 -14 28 -67
-26 -100 -45 55
3
18 -23 85 -71
-31 -30 7 -54
68 -33 -78 -21
3
-71 36 -11 -53
-43 -2 27 -31
-24 -30 10 71
3
-4 -26 74 -83
12 -86 -73 -58
50 -8...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #5:

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

input:

10
3
-747205 986354 -977580 581513
-666338 455489 -636199 888600
-729203 319266 -350608 -89261
3
-449879 -106071 923151 488259
-503807 220920 -120026 346138
110986 442433 -18303 -189764
3
-620049 -67194 -918363 -449594
848473 640562 267788 -183468
846086 972796 -635121 98853
3
-762212 49768 -558584 ...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 3816kb

input:

3333
3
1 0 0 0
1 1 -1 0
1 0 0 0
3
-1 0 1 0
1 0 1 -1
1 0 0 -1
3
-1 -1 0 -1
-1 -1 0 0
1 -1 1 1
3
1 1 0 -1
-1 0 0 0
0 0 1 0
3
-1 1 -1 0
-1 0 0 1
-1 -1 1 -1
3
0 -1 1 0
1 1 -1 -1
0 1 1 0
3
0 0 1 0
0 1 1 1
0 -1 0 0
3
1 1 -1 1
0 -1 -1 1
1 0 -1 0
3
1 1 -1 0
-1 1 1 0
0 0 -1 -1
3
-1 -1 -1 1
0 0 1 -1
-1 -1 1 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #7:

score: 0
Accepted
time: 5ms
memory: 3528kb

input:

3333
3
1 2 -2 2
2 0 0 1
0 -2 -1 0
3
-1 2 -2 1
-2 0 2 -2
0 -1 -1 -2
3
-1 0 -1 -2
2 -2 0 2
-2 -1 -1 1
3
-2 2 2 -2
2 0 -1 -2
1 2 -2 2
3
-2 -2 -2 0
-1 -2 1 -1
0 0 0 -2
3
-1 2 -2 1
1 2 1 0
0 -2 1 0
3
0 1 1 1
-1 -2 -2 -1
0 1 2 1
3
0 2 -2 1
-1 -2 -2 -2
1 2 2 1
3
2 1 2 -2
0 2 1 1
1 -2 1 0
3
1 -2 0 1
0 -1 -1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #8:

score: 0
Accepted
time: 8ms
memory: 3628kb

input:

3333
3
-3 0 1 -1
3 2 0 1
-3 1 3 -1
3
1 1 3 1
-3 1 2 -3
1 -1 2 1
3
3 -1 2 0
-1 2 -2 -1
-3 -1 0 2
3
-1 0 0 3
2 3 3 0
-2 2 2 -1
3
3 3 0 -3
2 0 0 0
1 -3 2 -3
3
2 -1 3 0
-2 2 -3 3
1 -2 1 3
3
-1 0 3 -2
-3 2 0 -2
-1 1 -3 -1
3
-1 -1 0 -1
0 1 0 -2
0 0 3 -3
3
2 2 -1 -1
2 -3 1 2
3 -2 3 1
3
2 2 1 3
2 0 1 2
2 2 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 3624kb

input:

3333
3
3 4 5 2
5 5 2 1
3 -3 5 0
3
-2 1 2 -3
-2 2 3 -1
-1 -5 -5 0
3
-4 3 1 1
5 5 3 -3
-5 -5 4 4
3
-4 2 1 1
-2 0 -3 0
2 5 2 -5
3
1 1 -4 -5
-3 -2 0 -2
-1 -4 5 -1
3
-5 -5 1 2
-5 1 2 2
0 -5 -1 -2
3
-3 -3 4 -1
-5 -5 -2 4
-2 3 -4 -1
3
4 3 2 1
5 -1 -5 2
-2 -1 -4 1
3
-4 2 2 3
-4 -1 3 -4
-2 -1 0 -4
3
4 0 2 3
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #10:

score: 0
Accepted
time: 8ms
memory: 3816kb

input:

3333
3
-73 -76 -14 11
90 73 50 -86
-90 64 -21 72
3
51 -82 -53 -63
-46 -40 -98 19
-33 -40 -13 -59
3
43 -81 4 76
41 -73 -88 -35
67 -8 21 25
3
-10 50 21 -96
5 36 -33 41
62 0 83 2
3
-20 22 33 63
-77 33 -69 -60
-69 -76 -87 -76
3
-9 80 -11 -53
-84 -100 59 -35
-78 67 -50 27
3
40 43 10 57
48 -31 58 82
22 53...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #11:

score: 0
Accepted
time: 9ms
memory: 3604kb

input:

3333
3
232210 724757 335359 -161206
-238348 644627 -349886 -46780
144753 304435 749031 494839
3
290483 -710209 121411 -413497
-811398 -54746 952122 -662175
-358336 475418 62077 209829
3
348229 607039 87835 824258
813712 -949811 829674 706963
638510 -881066 943199 890958
3
817602 715218 -96044 -56956...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #12:

score: 0
Accepted
time: 7ms
memory: 3576kb

input:

1000
10
1 0 0 0
-1 0 0 0
-1 -1 0 -1
0 1 1 0
-1 -1 1 -1
0 0 1 1
0 -1 1 1
-1 -1 0 1
0 0 -1 1
0 -1 1 0
10
1 0 1 -1
-1 0 1 0
0 1 1 0
1 0 1 -1
1 -1 1 0
1 -1 0 0
-1 1 1 1
0 0 1 1
-1 1 -1 0
0 0 0 1
10
-1 -1 0 1
-1 -1 -1 1
-1 1 1 -1
-1 1 -1 -1
-1 1 -1 0
-1 1 0 1
-1 0 -1 -1
0 1 0 -1
-1 -1 1 1
-1 0 1 -1
10
-1...

output:

1
2
0
0
0
1
1
2
3
0
0
0
0
0
2
2
3
2
0
0
1
0
0
0
0
0
1
1
2
0
28
0
0
0
0
0
0
0
0
5
0
0
2
0
1
1
0
3
0
10
0
4
2
1
1
0
0
0
1
0
0
1
1
0
0
1
1
4
5
0
0
1
0
5
1
1
3
0
0
3
0
2
0
0
8
0
0
1
0
0
0
1
4
0
2
0
3
1
0
0
3
2
0
0
0
3
2
0
0
5
0
0
5
1
0
1
7
0
0
1
1
1
8
0
0
0
0
0
0
2
0
0
1
0
0
1
0
3
2
2
7
1
1
2
3
2
3
0
0
...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 16ms
memory: 3612kb

input:

1000
10
2 -2 -1 -2
-2 0 2 2
0 1 0 2
-1 1 0 1
-1 -2 2 2
1 -1 -2 -1
0 2 1 2
-2 2 2 2
-2 -2 0 1
1 -2 1 -1
10
2 0 -1 1
1 0 -2 2
-1 -1 0 2
0 -2 1 2
-1 1 1 2
1 1 2 1
1 1 -2 2
2 1 -1 1
2 1 -2 2
-2 1 1 2
10
0 -2 -2 -2
2 -2 2 -1
1 -1 1 -2
-2 1 1 0
-2 -2 -1 -1
-1 1 -1 0
1 2 1 1
-1 2 1 -2
1 0 -1 2
-2 2 -1 0
10...

output:

1
0
0
1
1
0
1
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
3
0
2
0
0
2
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
0
0
2
1
2
0
0
1
1
0
0
0
1
0
0
0
3
0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
2
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
2
0
0
1
1
2
0
0
0
0
1
0
0
0
0
0
1
2
1
0
...

result:

ok 1000 numbers

Test #14:

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

input:

1000
10
2 -2 3 -2
-3 -3 1 -2
0 2 1 1
-3 2 2 3
3 2 0 0
-3 -3 -1 -1
1 2 -2 -3
0 3 -2 -1
1 3 2 3
3 0 -2 -1
10
-1 2 3 0
2 -2 2 3
-1 -3 -2 -2
2 0 -3 -3
-3 -1 1 2
-1 -2 -2 3
-3 0 2 3
3 1 1 -3
-2 -1 -2 1
2 3 1 2
10
-1 2 0 3
3 1 1 2
0 -3 -1 3
3 2 -3 -3
1 0 -1 -1
-1 -2 -3 3
-2 0 2 2
2 3 3 3
-3 0 1 3
1 -3 -1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
2
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
2
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #15:

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

input:

1000
10
5 1 5 -1
3 -4 5 4
-3 -3 5 -3
3 4 3 0
2 1 0 4
-2 4 3 2
-5 0 -1 4
-4 4 5 5
-4 5 5 1
3 2 3 -4
10
2 -1 -5 -3
-4 2 -4 0
-2 0 1 4
3 4 -5 5
4 -2 5 -5
-5 3 -5 -2
-3 5 4 2
2 -5 -5 -4
2 1 -3 -3
-3 3 -1 3
10
5 0 4 -4
-3 -4 5 3
-1 5 1 0
2 -5 4 2
-5 3 3 3
1 1 -3 1
3 -3 0 0
1 5 3 1
-1 -1 4 3
-4 -2 -1 1
10...

output:

0
0
0
0
0
1
0
0
0
2
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #16:

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

input:

1000
10
-81 -37 27 69
18 -90 -63 83
26 -83 -64 39
83 -31 -86 7
51 42 23 -50
100 0 52 -91
-24 32 -27 -93
-55 -5 -87 98
93 35 19 6
-20 21 30 -4
10
-82 4 -32 4
23 -4 99 1
-28 -78 95 0
95 34 67 -19
94 -74 -55 -70
-36 -89 15 96
65 50 -19 14
-45 -21 -13 -43
-91 -24 27 -93
-7 82 5 72
10
90 -20 -3 74
-53 -9...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #17:

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

input:

1000
10
707733 -556932 863167 188983
68093 883038 -523956 862355
447574 517286 -603738 12440
-44529 -487126 -44070 -341163
-556494 203231 -444122 614902
-949453 -616680 132221 -520744
85944 844890 -2105 796735
-515274 387669 -125589 133256
-279264 -478187 -74903 -822160
726839 -290815 754081 238246
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 2ms
memory: 3828kb

input:

100
100
1 1 -1 1
-1 1 1 0
1 1 0 -1
-1 1 1 -1
-1 1 1 -1
0 0 -1 0
1 0 0 0
1 -1 -1 1
1 1 -1 0
0 0 0 -1
-1 -1 -1 1
0 0 -1 1
0 0 1 -1
0 1 -1 1
-1 0 0 -1
-1 -1 0 -1
0 -1 -1 1
-1 -1 -1 0
-1 -1 0 1
-1 1 0 1
1 -1 0 1
0 0 -1 -1
1 -1 1 1
1 0 0 -1
1 -1 0 -1
0 0 -1 -1
0 1 -1 1
1 0 0 1
0 0 -1 1
1 -1 0 -1
1 -1 -1 ...

output:

1416
2459
716
1837
1612
1473
1330
1901
1646
2007
2216
2310
1915
1018
2194
1257
1139
1437
2265
1671
1245
1808
2182
1721
2454
1740
1830
2096
1433
1208
1246
1859
1141
1451
1631
1636
1472
1930
1328
2170
1307
1586
2022
1483
1346
1508
1665
1335
1045
1212
1799
1873
2130
1705
1993
1331
1621
1826
1206
1606
1...

result:

ok 100 numbers

Test #19:

score: 0
Accepted
time: 9ms
memory: 3608kb

input:

100
100
0 2 0 0
-1 2 1 -1
1 -2 0 2
0 2 0 1
1 2 0 1
-2 0 2 -1
-2 -1 2 1
0 0 2 -2
-2 -2 0 0
2 1 2 0
-1 -1 2 2
-1 -1 -2 0
0 2 2 -1
-2 1 0 0
1 1 2 0
0 1 2 0
-2 1 0 0
2 2 0 -2
2 -2 1 -1
-2 2 2 0
-1 2 -2 -1
-2 2 2 1
2 -2 1 2
0 1 2 2
1 1 1 -1
-1 0 0 -1
-1 -2 0 1
-1 0 2 1
-2 -1 -1 -2
1 2 1 -1
2 1 1 1
-1 2 1...

output:

827
600
712
457
698
849
478
738
690
791
460
637
391
814
820
767
709
889
568
832
623
828
687
578
600
606
1025
646
430
671
683
536
447
962
534
523
685
859
518
804
693
620
565
649
473
791
612
633
490
713
759
847
482
723
470
725
617
732
680
686
1025
918
544
857
928
867
607
684
958
445
953
652
681
786
81...

result:

ok 100 numbers

Test #20:

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

input:

100
100
-1 -3 1 3
-3 -2 2 1
-1 -1 -1 3
-2 -3 3 2
-1 3 -1 0
-1 -1 -1 1
-3 0 1 2
3 3 -3 0
2 3 -3 -2
0 3 -2 1
1 -2 2 1
0 -1 3 1
-1 1 3 -1
2 0 -3 -1
3 -1 -3 -3
-2 -2 -3 2
-3 1 3 0
-3 3 -1 3
2 -1 -1 3
2 1 1 -1
-3 3 -3 -2
3 -2 3 0
1 -1 -3 1
1 3 1 -2
1 3 0 -1
-2 -1 1 0
3 0 -2 1
-2 2 -2 3
-2 -1 1 2
1 2 3 -2...

output:

227
162
382
152
283
226
203
328
312
313
239
208
229
231
308
317
201
331
254
234
346
281
265
230
222
320
415
272
204
252
240
292
280
216
213
265
222
223
255
217
195
187
232
378
266
290
222
141
319
324
209
338
172
312
245
408
334
170
315
355
264
206
425
227
256
291
331
113
314
270
360
408
197
282
302
...

result:

ok 100 numbers

Test #21:

score: 0
Accepted
time: 79ms
memory: 4096kb

input:

100
100
-5 4 -5 -5
1 1 2 -2
2 0 3 -4
-3 0 0 3
-1 -1 -1 -3
4 -3 2 -3
4 -2 1 -2
5 -4 0 4
-5 -1 -3 0
3 0 -3 -5
-3 5 2 1
3 -1 -2 0
1 -2 -2 -1
-4 4 5 -1
-5 2 3 5
4 -4 -2 5
2 1 1 -4
3 5 -2 5
5 -5 3 5
3 0 -5 4
-4 4 -5 0
4 3 -3 -3
1 2 -2 -2
0 5 -4 3
-2 5 -4 -5
3 -2 3 0
-2 2 -1 3
4 -2 -1 -1
5 1 -2 -4
-2 3 4 ...

output:

46
101
71
89
67
36
68
137
48
79
92
52
112
58
68
51
55
63
62
62
51
82
63
61
101
68
80
57
51
75
108
63
68
60
81
106
95
59
56
59
94
76
80
115
69
87
98
86
52
36
54
73
77
39
55
67
77
86
48
68
88
70
111
70
46
36
73
53
31
79
89
81
68
60
57
115
48
87
80
65
38
58
92
87
77
41
76
81
80
52
86
66
99
43
167
53
52...

result:

ok 100 numbers

Test #22:

score: 0
Accepted
time: 325ms
memory: 4460kb

input:

100
100
-84 -92 19 -8
-5 -45 98 -88
67 -21 -97 -78
41 -5 -41 -43
-39 65 -15 63
-40 -59 11 7
-55 -38 12 -52
-34 -71 -9 34
-29 -66 54 -99
-37 -43 -100 91
-30 -45 35 -80
-88 48 -43 24
-98 -49 47 62
-94 15 67 38
75 -62 -70 58
37 34 43 93
-20 93 99 -11
-22 90 99 70
-59 -34 47 -10
72 -78 1 -60
-12 36 -18 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 numbers

Test #23:

score: 0
Accepted
time: 306ms
memory: 4504kb

input:

100
100
-98638 225635 357945 -62503
594854 -376508 -284287 -261261
-973554 -174291 -101939 -545390
-553498 -357731 -341552 773471
-98840 424051 -863787 792215
-203496 -170606 970526 161347
523886 636459 41663 -281463
92 560351 -455508 226905
321343 -94412 423559 -810680
414569 647593 555629 -70290
5...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

10
1000
-1 1 1 -1
0 1 1 0
1 0 1 -1
1 1 1 -1
1 0 -1 -1
-1 0 0 0
-1 -1 1 0
-1 1 0 1
0 1 0 -1
1 -1 -1 -1
-1 0 1 1
0 1 1 0
0 0 1 -1
1 1 0 -1
-1 1 1 1
-1 -1 1 1
1 1 -1 0
0 0 -1 -1
1 1 0 0
1 -1 0 1
0 1 1 1
1 1 -1 1
1 1 -1 1
0 0 0 -1
-1 0 1 0
1 -1 1 1
-1 0 1 0
-1 1 1 1
1 0 -1 1
1 0 1 1
1 1 0 0
1 1 0 0
-1 -...

output:

1737797
1594271
1713514
1781504
1593707
1632002
1680399
1731213
1930935
1440704

result:

ok 10 numbers

Test #25:

score: 0
Accepted
time: 7ms
memory: 3708kb

input:

10
1000
-2 -2 0 -2
2 2 -1 -2
2 2 -2 -2
-2 -1 -2 -2
-1 1 0 1
-1 1 1 0
2 -2 -1 1
2 -2 -1 -1
2 2 -1 1
2 -1 -1 0
0 2 -2 1
1 0 -2 -1
1 -2 1 1
2 1 -1 -1
0 0 -1 2
2 1 -2 2
-1 2 -2 1
-1 0 0 0
0 0 2 -2
-1 1 1 -2
0 2 1 2
1 -2 1 0
2 0 0 2
-1 1 2 1
-1 0 -2 0
-1 1 -1 0
1 -2 2 -2
1 1 2 1
-2 2 0 1
1 0 2 2
-1 -1 1 ...

output:

722935
746226
680940
634492
736540
699343
679979
783183
667962
673500

result:

ok 10 numbers

Test #26:

score: 0
Accepted
time: 12ms
memory: 3736kb

input:

10
1000
-1 1 3 2
-2 3 2 0
2 1 3 1
2 3 1 1
1 -3 0 -1
0 3 -2 -3
-2 -1 -2 2
0 0 1 -2
1 1 0 2
-3 2 -2 2
0 -3 -1 1
-3 -3 2 -1
-1 3 0 -3
3 1 -3 -2
-2 -1 -3 2
0 2 2 -3
3 3 3 0
2 0 -2 -1
0 -1 1 2
2 2 0 -2
-2 3 0 -3
0 -3 1 0
2 -3 -2 2
-3 -3 1 1
1 3 3 -2
-2 3 -1 3
2 -2 1 3
-1 3 0 -3
0 1 2 -2
1 -2 -3 2
-1 -2 1...

output:

299570
308269
290907
264415
261421
247904
304793
278099
288701
288442

result:

ok 10 numbers

Test #27:

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

input:

10
1000
0 3 5 0
-2 -2 -1 -1
0 -4 5 -2
-2 -4 4 5
-5 1 -3 -5
-4 -1 -4 2
-3 -5 2 4
4 4 0 -1
-1 -1 3 3
-2 -1 2 -4
-1 -3 -1 -2
1 -2 2 -5
0 5 3 3
0 -4 0 1
-2 -5 -4 -5
-5 -1 2 -1
1 0 2 3
-3 -4 2 2
-1 0 0 -1
2 -3 5 5
3 -1 3 3
-4 -5 -5 0
2 -4 4 -1
5 -3 -4 3
-1 0 0 5
-3 4 5 0
-4 -1 -2 0
2 -4 -5 -3
4 2 1 -1
4 ...

output:

67389
73481
75956
73349
70649
68453
70949
75789
66922
65244

result:

ok 10 numbers

Test #28:

score: -100
Time Limit Exceeded

input:

10
1000
-3 0 3 -11
4 -77 18 -90
-83 -82 -9 -97
-77 93 -99 80
-85 12 -12 -21
8 -28 13 24
-43 34 -62 -77
26 88 -41 -65
67 37 -46 100
56 35 -75 3
-19 -25 -17 -14
-36 -92 -18 48
-74 -34 -4 -100
-55 31 75 -18
-3 -13 -9 -51
21 32 -31 -82
-6 1 76 46
50 -59 33 -19
73 78 58 28
-12 34 -32 50
-99 -92 -83 -79
4...

output:


result: