QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373021 | #5276. K-Shaped Figures | kevinyang# | TL | 532ms | 4212kb | C++17 | 5.7kb | 2024-03-31 23:33:57 | 2024-03-31 23:33:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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;
map<pair<int,int>,int>have;
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];
have[{u,v}]++;
have[{v,u}]++;
a[i] = {u,v};
}
assert(arr.size()==m);
vector<vector<int>>adj(m);
map<int,int>hid;
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<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.count({hm[arr[l]],hm[arr[r]]})){
int mul = have[{hm[arr[l]],hm[arr[r]]}];
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: 1ms
memory: 3520kb
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: 3616kb
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: 1ms
memory: 3848kb
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: 1ms
memory: 3644kb
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: 3852kb
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: 11ms
memory: 3868kb
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: 13ms
memory: 3668kb
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: 12ms
memory: 3584kb
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: 13ms
memory: 3876kb
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: 11ms
memory: 3616kb
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: 12ms
memory: 3648kb
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: 12ms
memory: 3580kb
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: 26ms
memory: 3680kb
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: 33ms
memory: 3828kb
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: 37ms
memory: 3836kb
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: 36ms
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: 36ms
memory: 3588kb
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: 7ms
memory: 3592kb
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: 17ms
memory: 3836kb
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: 39ms
memory: 3732kb
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: 123ms
memory: 3748kb
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: 532ms
memory: 4000kb
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: 473ms
memory: 4212kb
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: 4ms
memory: 3640kb
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: 11ms
memory: 3972kb
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: 20ms
memory: 3772kb
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: 41ms
memory: 4112kb
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...