QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373029 | #5276. K-Shaped Figures | kevinyang# | TL | 325ms | 4504kb | C++17 | 5.9kb | 2024-03-31 23:42:17 | 2024-03-31 23:42:46 |
Judging History
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;
}
详细
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...