QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111880 | #6570. Who Watches the Watchmen? | KhNURE_KIVI | AC ✓ | 1702ms | 20508kb | C++20 | 15.6kb | 2023-06-09 04:30:36 | 2023-06-09 04:30:39 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
inline bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL
const int max_n = -1, inf = 1000111222;
struct node {
ll x, y, z, a, b, c;
};
inline bool check_eq (ll a, ll b, ll d, ll div) {
return a * div == d * b;
}
namespace MIN_COST_MAX_FLOW {
/// source: https://codeforces.com/contest/1572/submission/129205002
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
typedef ll Flow;
typedef ll Cost;
const Flow FLOW_INF = 1LL<<60;
const Cost COST_INF = 1LL<<60;
const int SIZE = 65;
vector<pair<Cost, int> > B[SIZE];
Cost last;
int sz;
int bsr(Cost c) {
if (c == 0) return 0;
return __lg(c)+1;
}
void init() {
last = sz = 0;
REP (i, SIZE) B[i].clear();
}
void push(Cost cst, int v) {
assert(cst >= last);
sz++;
B[bsr(cst^last)].emplace_back(cst, v);
}
pair<Cost, int> pop_min() {
assert(sz);
if (B[0].empty()) {
int k = 1;
while (k < SIZE && B[k].empty()) k++;
assert(k < SIZE);
last = B[k][0].first;
EACH (e, B[k]) umin(last, e->first);
EACH (e, B[k]) B[bsr(e->first^last)].push_back(*e);
B[k].clear();
}
assert(B[0].size());
pair<Cost, int> ret = B[0].back();
B[0].pop_back();
sz--;
return ret;
}
struct MinCostMaxFlow {
struct Edge {
int dst;
Cost cst;
Flow cap;
int rev;
};
typedef vector<vector<Edge> > Graph;
Graph G;
bool negative_edge;
MinCostMaxFlow(int N) : G(N) {
negative_edge = false;
}
void add_edge(int u, int v, Cost x, Flow f) {
if (u == v) return;
if (x < 0) negative_edge = true;
G[u].push_back((Edge){ v, x, f, (int)G[v].size() });
G[v].push_back((Edge){ u, -x, 0, (int)G[u].size()-1 });
}
void bellman_ford(int s, vector<Cost> &h) {
fill(h.begin(), h.end(), COST_INF);
vector<bool> in(G.size());
h[s] = 0;
in[s] = true;
vector <int> front, back;
front.push_back(s);
while (1) {
if (front.empty()) {
if (back.empty()) return;
swap(front, back);
reverse(front.begin(), front.end());
}
int v = front.back(); front.pop_back();
in[v] = false;
EACH (e, G[v]) if (e->cap) {
int w = e->dst;
if (h[w] > h[v] + e->cst) {
h[w] = h[v] + e->cst;
if (!in[w]) {
back.push_back(w);
in[w] = true;
}
}
}
}
}
Flow flow;
Cost cost;
Flow solve(int s, int t, Flow limit = FLOW_INF) {
flow = 0;
cost = 0;
vector<Cost>len1(G.size()), h(G.size());
if (negative_edge) bellman_ford(s, h);
vector<int> prev(G.size()), prev_num(G.size());
while (limit > 0) {
init(); push(0, s);
fill(len1.begin(), len1.end(), COST_INF);
fill(prev.begin(), prev.end(), -1);
len1[s] = 0;
while (sz) {
pair<Cost, int> p = pop_min();
Cost cst = p.first;
int v = p.second;
if (cst > len1[v]) continue;
for (int i=0; i<(int)G[v].size(); i++) {
const Edge &f = G[v][i];
Cost tmp = len1[v] + f.cst + h[v] - h[f.dst];
if (f.cap > 0 && len1[f.dst] > tmp) {
len1[f.dst] = tmp;
push(tmp, f.dst);
prev[f.dst] = v; prev_num[f.dst] = i;
}
}
}
if (prev[t] == -1) return flow;
for (int i=0; i<(int)G.size(); i++) h[i] += len1[i];
Flow f = limit;
for (int v=t; v!=s; v=prev[v])
f = min(f, G[prev[v]][prev_num[v]].cap);
for (int v=t; v!=s; v=prev[v]) {
Edge &e = G[prev[v]][prev_num[v]];
e.cap -= f;
G[e.dst][e.rev].cap += f;
}
limit -= f;
flow += f;
cost += f * h[t];
}
return flow;
}
};
}; // namespace MIN_COST_MAX_FLOW;
using MinCostMaxFlow = MIN_COST_MAX_FLOW::MinCostMaxFlow;
namespace math {
inline ll det (ll a, ll b, ll c, ll d) {
return a * d - b * c;
}
inline pair<pair<ll, ll>, pair<ll, ll> > solve (ll xa1, ll ya1, ll c1, ll xa2, ll ya2, ll c2) {
ll d = det(xa1, ya1, xa2, ya2);
// debug(xa1, ya1, c1, xa2, ya2, c2);
if (d == 0) {
return {{-1, 0}, {-1, 0}};
}
ll x = det(c1, ya1, c2, ya2);
ll y = det(xa1, c1, xa2, c2);
return {{x, d}, {y, d}};
}
}
using big = __int128;
inline bool check_good (pair<pair<ll, ll>, pair<ll, ll> > gg, ll a, ll b, ll c) {
return big(a) * big(gg.first.first) * big(gg.second.second) +
big(b) * big(gg.first.second) * big(gg.second.first)
+ big(c) * big(gg.first.second) * big(gg.second.second) == 0;
};
inline bool check_pos (pair<ll, ll> a) {
LOG(a.first, a.second);
if (a.first < 0) {
a.first *= -1;
a.second *= -1;
}
if (a.first == 0) {
a.second = abs(a.second);
}
return a.second > 0 && a.first > 0;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <node> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y >> a[i].z >> a[i].a >> a[i].b >> a[i].c;
}
if (n == 1) {
cout << "-1\n";
return 0;
}
auto check = [&] (int i, int j, ll akx, ll aky, ll akz, bool what = false) {
ll A = a[j].x - a[i].x;
ll B = a[j].y - a[i].y;
ll C = a[j].z - a[i].z;
ll d = 0;
ll div = 0;
if (!A) {
if (a[i].x != akx) {
return false;
}
}
else {
d = akx - a[i].x;
div = A;
}
if (!B) {
if (a[i].y != aky) {
return false;
}
}
else {
d = aky - a[i].y;
div = B;
}
if (!C) {
if (a[i].z != akz) {
return false;
}
}
else {
d = akz - a[i].z;
div = C;
}
if (A) {
if (!check_eq(akx - a[i].x, A, d, div)) {
return false;
}
}
if (B) {
if (!check_eq(aky - a[i].y, B, d, div)) {
return false;
}
}
if (C) {
if (!check_eq(akz - a[i].z, C, d, div)) {
return false;
}
}
if (d < 0) {
d *= -1;
div *= -1;
}
assert(d != 0);
if (div < 0) {
return false;
}
if (what) {
return true;
}
if (d < div) {
return true;
}
return false;
};
vector <vector <int> > c(n, vector <int> (n, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
bool ok = true;
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
if (check(i, j, a[k].x, a[k].y, a[k].z)) {
ok = false;
break;
}
}
if (ok) {
c[i][j] = 1;
ll tox = a[i].x + a[i].a;
ll toy = a[i].y + a[i].b;
ll toz = a[i].z + a[i].c;
if (check(i, j, tox, toy, toz, true)) {
c[i][j] = 0;
}
}
}
}
MinCostMaxFlow g(2 * n + 2);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] == -1) {
continue;
}
//LOG(i, j, c[i][j]);
g.add_edge(i + 1, n + 1 + j, c[i][j], 1);
}
g.add_edge(0, i + 1, 0, 1);
g.add_edge(n + i + 1, 2 * n + 1, 0, 1);
}
int ans = g.solve(0, 2 * n + 1);
LOG(ans);
if (ans != n) {
ans = inf;
int pos = -1;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (c[i][j] == -1) {
continue;
}
++cnt;
}
assert(cnt <= 2);
if (cnt == 1) {
pos = i;
}
}
vector <int> used(n);
vector <int> order;
for (int i = 0; i < n; i++) {
LOG(pos);
order.pb(pos);
used[pos] = 1;
int to = -1;
for (int j = 0; j < n; j++) {
if (c[pos][j] == -1 || used[j]) {
continue;
}
to = j;
}
pos = to;
}
auto solve = [&] () {
for (int i = 0; i < n; i++) {
vector <int> new_order;
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
new_order.pb(order[j]);
}
int I = order[i];
LOG(I, a[I].x, a[I].y, a[i].z);
order.swap(new_order);
vector<int> pref(n, inf), suff(n, inf);
int val = 0;
suff[n - 1] = 0;
ll A, B, C;
for (int j = 1; j < n - 1; j += 2) {
A = a[order[j - 1]].x + a[order[j - 1]].a;
B = a[order[j - 1]].y + a[order[j - 1]].b;
C = a[order[j - 1]].z + a[order[j - 1]].c;
if (!check(order[j - 1], order[j], A, B, C, true)) {
++val;
}
A = a[order[j]].x + a[order[j]].a;
B = a[order[j]].y + a[order[j]].b;
C = a[order[j]].z + a[order[j]].c;
if (!check(order[j], order[j - 1], A, B, C, true)) {
++val;
}
pref[j] = val;
}
val = 0;
for (int j = n - 2; j > 0; j -= 2) {
A = a[order[j - 1]].x + a[order[j - 1]].a;
B = a[order[j - 1]].y + a[order[j - 1]].b;
C = a[order[j - 1]].z + a[order[j - 1]].c;
if (!check(order[j - 1], order[j], A, B, C, true)) {
++val;
}
A = a[order[j]].x + a[order[j]].a;
B = a[order[j]].y + a[order[j]].b;
C = a[order[j]].z + a[order[j]].c;
if (!check(order[j], order[j - 1], A, B, C, true)) {
++val;
}
suff[j - 1] = val;
}
int prf = 0;
for (int fst = 0; fst < n - 1; fst += 2) {
int cur = 1000 + prf;
int last = -1, f = -1;
for (int j = fst; j < n - 1; j++) {
if (last != -1) {
if (!check(last, order[j], A, B, C, true)) {
++cur;
}
}
if (f == -1) {
f = order[j];
}
last = order[j];
A = a[order[j]].x + a[order[j]].a;
B = a[order[j]].y + a[order[j]].b;
C = a[order[j]].z + a[order[j]].c;
int res = cur + suff[j + 1];
if (j == fst) {
ll AA = a[order[j]].x + a[order[j]].a;
ll BB = a[order[j]].y + a[order[j]].b;
ll CC = a[order[j]].z + a[order[j]].c;
if (!check(order[j], I, AA, BB, CC, true)) {
++res;
}
AA = a[I].x + a[I].a;
BB = a[I].y + a[I].b;
CC = a[I].z + a[I].c;
if (check(I, order[j], AA, BB, CC, true)
|| check(order[j], I, AA, BB, CC, true)) {
++res;
}
umin(ans, res);
continue;
}
ll xx = A - a[last].x;
ll yy = B - a[last].y;
ll zz = C - a[last].z;
ll tx = a[I].a;
ll ty = a[I].b;
ll tz = a[I].c;
ll tx1 = -(a[f].x - a[last].x);
ll ty1 = -(a[f].y - a[last].y);
ll tz1 = -(a[f].z - a[last].z);
if (math::det(tx, tx1, tz, tz1)) {
auto gg = math::solve(tx, tx1, -xx, tz, tz1, -zz);
if (!check_good(gg, ty, ty1, yy) || !check_pos(gg.first) || !check_pos(gg.second)) {
++res;
}
} else if (math::det(tx, tx1, ty, ty1)) {
auto gg = math::solve(tx, tx1, -xx, ty, ty1, -yy);
if (!check_good(gg, tz, tz1, zz) || !check_pos(gg.first) || !check_pos(gg.second)) {
++res;
}
} else if (math::det(ty, ty1, tz, tz1)) {
auto gg = math::solve(ty, ty1, -yy, tz, tz1, -zz);
if (!check_good(gg, tx, tx1, xx) || !check_pos(gg.first) || !check_pos(gg.second)) {
++res;
}
} else {
++res;
if (check(last, f, A, B, C, true) ||
check(f, last, A, B, C, true)) {
++res;
}
}
LOG(fst, j, I, res);
umin(ans, res);
}
prf = pref[fst + 1];
}
order.swap(new_order);
}
};
solve();
reverse(all(order));
solve();
cout << ans << '\n';
return 0;
}
cout << g.cost << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3368kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1002
result:
ok single line: '1002'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
4 66 45 10 73 39 36 95 14 26 47 84 59 14 66 89 89 36 78 16 27 94 79 24 24
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
3 0 0 0 1 0 0 1 1 1 1 0 0 2 2 2 1 0 0
output:
1002
result:
ok single line: '1002'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3356kb
input:
3 0 0 0 1 1 1 1 1 1 1 0 0 2 2 2 1 0 0
output:
1001
result:
ok single line: '1001'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
3 0 0 0 1 0 0 1 1 1 1 0 0 2 2 2 -1 -1 -1
output:
1001
result:
ok single line: '1001'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
3 0 0 0 1 0 0 1 1 1 1 2 2 2 2 2 -1 -1 -1
output:
1000
result:
ok single line: '1000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3348kb
input:
3 0 0 0 1 0 0 1 1 1 1 2 2 2 2 2 1 1 1
output:
1001
result:
ok single line: '1001'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
1 0 0 0 3 1 4
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
4 0 0 0 1 1 1 1 0 0 -1 0 0 1 1 1 0 -1 0 1 0 1 0 1 0
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 171ms
memory: 4624kb
input:
500 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1 0 0...
output:
250
result:
ok single line: '250'
Test #11:
score: 0
Accepted
time: 178ms
memory: 4620kb
input:
500 0 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1 0...
output:
250
result:
ok single line: '250'
Test #12:
score: 0
Accepted
time: 193ms
memory: 4628kb
input:
500 0 0 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1...
output:
250
result:
ok single line: '250'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
5 1 0 0 1 -1 0 2 0 0 0 1 0 3 0 0 -1 0 0 4 0 0 -1 0 0 5 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
5 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 0 1 0 5 0 0 -1 -1 0
output:
1000
result:
ok single line: '1000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
6 0 1 0 1 0 0 0 2 0 0 2 0 0 3 0 0 3 0 0 4 0 0 4 0 0 5 0 0 5 0 0 6 0 0 6 0
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
9 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 1655ms
memory: 4628kb
input:
499 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1 0 0...
output:
1220
result:
ok single line: '1220'
Test #18:
score: 0
Accepted
time: 1622ms
memory: 4680kb
input:
499 0 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1 0...
output:
1220
result:
ok single line: '1220'
Test #19:
score: 0
Accepted
time: 1702ms
memory: 4628kb
input:
499 0 0 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0 11 0 0 -1 0 0 12 0 0 1 0 0 13 0 0 -1 0 0 14 0 0 1 0 0 15 0 0 1 0 0 16 0 0 1 0 0 17 0 0 -1 0 0 18 0 0 -1 0 0 19 0 0 -1 0 0 20 0 0 -1 0 0 21 0 0 1 0 0 22 0 0 1...
output:
1220
result:
ok single line: '1220'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
5 0 0 0 0 -1 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 1 0 0
output:
1001
result:
ok single line: '1001'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
5 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 0 1 0
output:
1001
result:
ok single line: '1001'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
5 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 0 -1 0 3 0 0 1 0 0 4 0 0 -1 0 0
output:
1001
result:
ok single line: '1001'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
5 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 0 -1 0 4 0 0 1 0 0
output:
1001
result:
ok single line: '1001'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
5 0 0 0 1 1 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 -1 -1 0
output:
1001
result:
ok single line: '1001'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
5 0 0 0 1 1 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 1 1 0
output:
1001
result:
ok single line: '1001'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
5 0 0 0 5 -1 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 0 1 -1 0
output:
1001
result:
ok single line: '1001'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
17 0 0 0 0 0 1 0 1 0 0 0 1 0 2 0 0 0 1 0 3 0 0 0 1 0 4 0 0 0 1 0 -1 0 0 0 1 0 -2 0 0 0 1 0 -3 0 0 0 1 0 -4 0 0 0 1 1 3 0 0 0 1 2 3 0 0 0 1 -1 3 0 0 0 1 -2 3 0 0 0 1 1 -3 0 0 0 1 2 -3 0 0 0 1 -1 -3 0 0 0 1 -2 -3 0 0 0 1
output:
17
result:
ok single line: '17'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
17 0 0 0 0 4 0 0 1 0 0 -1 0 0 2 0 0 -2 0 0 3 0 0 -3 0 0 4 0 0 -4 0 0 -1 0 0 1 0 0 -2 0 0 2 0 0 -3 0 0 3 0 0 -4 0 0 4 0 1 3 0 -1 -3 0 2 3 0 -1 -2 0 -1 3 0 1 -3 0 -2 3 0 2 -3 0 1 -3 0 -1 3 0 2 -3 0 -2 3 0 -1 -3 0 1 3 0 -2 -3 0 2 3 0
output:
10
result:
ok single line: '10'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
17 0 0 0 0 1 0 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 2 -1 0 0 -1 0 0 1 0 0 -2 0 0 1 0 0 -3 0 0 1 0 0 -4 0 0 1 0 1 3 0 -1 0 0 2 3 0 -1 0 0 -1 3 0 -1 0 0 -2 3 0 4 -6 0 1 -3 0 -1 0 0 2 -3 0 -1 0 0 -1 -3 0 -1 0 0 -2 -3 0 2 -1 0
output:
3
result:
ok single line: '3'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
5 0 0 0 1 1 1 0 0 1 0 0 1 0 0 2 0 0 1 0 0 3 0 0 1 0 0 4 0 -1 1
output:
1001
result:
ok single line: '1001'
Test #31:
score: 0
Accepted
time: 943ms
memory: 20344kb
input:
500 -455212 958307 274912 -88656 390687 881409 -498879 -623821 322766 -916023 347922 541726 -594515 -554311 -413504 -881701 -506880 -144667 658945 -503396 791805 314816 -830920 -769486 -200847 845218 468338 -166468 -49854 -287877 -820402 914874 916800 258029 -210000 -296727 702016 -389491 -31529 -52...
output:
499
result:
ok single line: '499'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
3 1000000 -1 -1 -1000000 -999999 -999999 -1 1000000 -1 101 -101 0 100 999899 -1 999999 1000000 999999
output:
1000
result:
ok single line: '1000'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
3 1000000 -1 -1 1000000 999999 999999 -1 1000000 -1 101 -101 0 100 999899 -1 999999 1000000 999999
output:
1001
result:
ok single line: '1001'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3368kb
input:
3 1000000 -1 -1 -1000000 -999999 -999999 -1 1000000 -1 101 -101 0 100 999899 -1 -999999 -1000000 -999999
output:
1001
result:
ok single line: '1001'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3352kb
input:
3 1000000 -1 -1 1000000 999999 999999 -1 1000000 -1 101 -101 0 100 999899 -1 -999999 -1000000 -999999
output:
1001
result:
ok single line: '1001'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
3 10 -1 -1 -10 -9 -9 -1 10 -1 11 -11 0 21 -12 -1 9 10 9
output:
1000
result:
ok single line: '1000'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 0 -1 0 3 0 0 1 0 0 4 0 0 -1 1 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
7 0 0 0 1 0 0 1 0 0 0 -1 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 -1 1 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
7 0 0 0 0 -1 0 1 0 0 1 0 0 2 0 0 -1 0 0 3 0 0 1 0 0 4 0 0 -1 1 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3380kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 1 0 4 0 0 0 -1 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 1 0 4 0 0 1 0 0 5 0 0 0 -1 0 6 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3360kb
input:
7 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 1 0 4 0 0 1 0 0 5 0 0 -1 0 0 6 0 0 0 -1 0
output:
1000
result:
ok single line: '1000'
Test #43:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 0 1 0 5 0 0 1 -1 0 6 0 0 -1 0 0 7 0 0 -1 0 0 8 0 0 -1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 1 -1 0 5 0 0 0 1 0 6 0 0 -1 0 0 7 0 0 -1 0 0 8 0 0 -1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #45:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 0 1 0 5 0 0 -1 0 0 6 0 0 1 -1 0 7 0 0 -1 0 0 8 0 0 -1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #46:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 0 1 0 5 0 0 -1 0 0 6 0 0 -1 0 0 7 0 0 1 -1 0 8 0 0 -1 0 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #47:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 -1 -1 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 0 1 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #48:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 1 0 0 5 0 0 -1 -1 0 6 0 0 1 0 0 7 0 0 1 0 0 8 0 0 0 1 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #49:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 -1 -1 0 7 0 0 1 0 0 8 0 0 0 1 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 -1 -1 0 8 0 0 0 1 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #51:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
11 0 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 1 0 0 3 0 0 -1 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 1 0 0 7 0 0 0 1 0 8 0 0 -1 -1 0 9 0 0 1 0 0 10 0 0 -1 0 0
output:
1000
result:
ok single line: '1000'
Test #52:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
27 -1000000 -1000000 -1000000 1000000 0 1000000 -1000000 -1000000 0 -1000000 0 1000000 -1000000 -1000000 1000000 -1000000 0 1000000 -1000000 0 -1000000 1000000 1000000 1000000 -1000000 0 0 0 -1000000 1000000 -1000000 0 1000000 1000000 -1000000 1000000 -1000000 1000000 -1000000 1000000 0 1000000 -100...
output:
17
result:
ok single line: '17'
Test #53:
score: 0
Accepted
time: 223ms
memory: 4636kb
input:
500 -999983 -999981 -999977 17 19 23 -999966 -999962 -999954 17 19 23 -999949 -999943 -999931 17 19 23 -999932 -999924 -999908 17 19 23 -999915 -999905 -999885 17 19 23 -999898 -999886 -999862 17 19 23 -999881 -999867 -999839 17 19 23 -999864 -999848 -999816 17 19 23 -999847 -999829 -999793 17 19 23...
output:
250
result:
ok single line: '250'
Test #54:
score: 0
Accepted
time: 216ms
memory: 4632kb
input:
500 999983 999981 999977 -17 -19 -23 999966 999962 999954 -17 -19 -23 999949 999943 999931 -17 -19 -23 999932 999924 999908 -17 -19 -23 999915 999905 999885 -17 -19 -23 999898 999886 999862 -17 -19 -23 999881 999867 999839 -17 -19 -23 999864 999848 999816 -17 -19 -23 999847 999829 999793 -17 -19 -23...
output:
250
result:
ok single line: '250'
Test #55:
score: 0
Accepted
time: 226ms
memory: 4680kb
input:
500 999686 -999841 999735 -314 159 -265 999372 -999682 999470 -314 159 -265 999058 -999523 999205 314 -159 265 998744 -999364 998940 -314 159 -265 998430 -999205 998675 -314 159 -265 998116 -999046 998410 -314 159 -265 997802 -998887 998145 -314 159 -265 997488 -998728 997880 -314 159 -265 997174 -9...
output:
250
result:
ok single line: '250'
Test #56:
score: 0
Accepted
time: 226ms
memory: 4620kb
input:
500 999900 -999800 999700 -100 200 -300 999800 -999600 999400 -100 200 -300 999700 -999400 999100 100 -200 300 999600 -999200 998800 -100 200 -300 999500 -999000 998500 -100 200 -300 999400 -998800 998200 -100 200 -300 999300 -998600 997900 -100 200 -300 999200 -998400 997600 -100 200 -300 999100 -9...
output:
250
result:
ok single line: '250'
Test #57:
score: 0
Accepted
time: 28ms
memory: 4556kb
input:
480 -2402 3028 3274 23 -29 -31 -79 99 143 23 -29 -31 3854 -4860 -5158 -23 29 31 1370 -1728 -1810 -23 29 31 -4127 5203 5599 23 -29 -31 -5461 6885 7397 23 -29 -31 2382 -3004 -3174 -23 29 31 -1965 2477 2685 23 -29 -31 2888 -3642 -3856 -23 29 31 -3782 4768 5134 23 -29 -31 1899 -2395 -2523 -23 29 31 59 -...
output:
122
result:
ok single line: '122'
Test #58:
score: 0
Accepted
time: 32ms
memory: 4556kb
input:
480 43422 13353 -25668 414 129 -256 1608 324 188 414 129 -256 -69186 -21735 43964 -414 -129 256 -24474 -7803 16316 -414 -129 256 74472 23028 -44868 414 129 -256 98484 30510 -59716 414 129 -256 -42690 -13479 27580 -414 -129 256 35556 10902 -20804 414 129 -256 -51798 -16317 33212 -414 -129 256 68262 2...
output:
123
result:
ok single line: '123'
Test #59:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
180 375 636 1057 -4 -8 -12 47 -20 73 4 8 12 331 548 925 -4 -8 -12 -29 -172 -155 4 8 12 -153 -420 -527 4 8 12 427 740 1213 -4 -8 -12 -173 -460 -587 4 8 12 -241 -596 -791 4 8 12 179 244 469 -4 -8 -12 159 204 409 -4 -8 -12 -161 -436 -551 4 8 12 399 684 1129 -4 -8 -12 223 332 601 -4 -8 -12 59 4 109 -4 -...
output:
42
result:
ok single line: '42'
Test #60:
score: 0
Accepted
time: 8ms
memory: 3780kb
input:
220 27 -85 15 12 8 4 927 515 315 -12 -8 -4 -93 -165 -25 12 8 4 1083 619 367 -12 -8 -4 39 -77 19 12 8 4 -1281 -957 -421 12 8 4 1143 659 387 -12 -8 -4 183 19 67 -12 -8 -4 1047 595 355 -12 -8 -4 567 275 195 -12 -8 -4 531 251 183 -12 -8 -4 -177 -221 -53 12 8 4 579 283 199 -12 -8 -4 -561 -477 -181 12 8 4...
output:
52
result:
ok single line: '52'
Test #61:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
60 -171 215 267 23 -29 -31 473 -597 -601 -23 29 31 312 -394 -384 -23 29 31 404 -510 -508 -23 29 31 197 -249 -229 -23 29 31 335 -423 -415 -23 29 31 -654 824 918 23 -29 -31 -493 621 701 23 -29 -31 565 -713 -725 -23 29 31 -217 273 329 23 -29 -31 -631 795 887 23 -29 -31 496 -626 -632 -23 29 31 -447 563 ...
output:
17
result:
ok single line: '17'
Test #62:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
3 -1 0 0 2 1 0 1 0 0 -2 1 0 3 0 0 -2 -1 0
output:
1001
result:
ok single line: '1001'
Test #63:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
5 0 0 0 0 1 0 10 0 0 -1 1 0 0 10 0 -1 -1 0 -10 0 0 1 -1 0 0 -10 0 1 1 0
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
5 0 2 0 0 1 0 10 0 0 -1 1 0 0 10 0 -1 -1 0 -10 0 0 1 -1 0 0 -10 0 1 1 0
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 955ms
memory: 20344kb
input:
500 464689 -654475 874948 278641 -792884 186354 -798268 -885245 366579 415873 -814492 568386 548594 757214 459960 -318745 -320885 285634 -970144 68165 91372 -935576 -557281 -82177 -71496 697792 859229 603072 -751718 -629380 -391402 -320266 -691800 99295 771407 -415586 131176 -704350 628899 959024 80...
output:
500
result:
ok single line: '500'
Test #66:
score: 0
Accepted
time: 930ms
memory: 20508kb
input:
500 660575 -715271 73415 436140 226362 12224 19467 916145 -662062 -510604 824283 454499 205202 -915814 -735123 -110822 -83586 808202 13120 -72969 106150 -211607 557293 169887 -5849 149098 -624091 831479 -195891 -854258 335561 -450902 467595 -612441 695943 -877490 -356999 -751820 -886079 499927 46503...
output:
500
result:
ok single line: '500'
Test #67:
score: 0
Accepted
time: 940ms
memory: 20488kb
input:
500 -425261 857089 -722463 345227 -983886 -779314 873569 -40018 -490178 580005 -863510 -254613 -435240 -520380 84908 -513784 564739 330588 -932188 -477605 -347322 492032 -294079 477227 -72311 862368 -29594 -887377 -627667 -608677 -775504 -953650 8567 -11911 -162415 -485409 822275 -380961 773749 9387...
output:
500
result:
ok single line: '500'
Test #68:
score: 0
Accepted
time: 909ms
memory: 20496kb
input:
500 -132886 502058 -877447 79042 35022 -322286 101780 -909854 172531 103616 -119015 -271777 289064 -256857 -663836 977205 -748931 -999133 -68650 848633 -3718 -874892 260143 -880264 399836 -18330 881394 -913991 761700 620864 642012 105194 -288186 637083 -765709 -480047 -818650 -112345 310067 -918378 ...
output:
500
result:
ok single line: '500'
Test #69:
score: 0
Accepted
time: 951ms
memory: 20364kb
input:
500 -455212 958307 274912 -88656 390687 881409 -498879 -623821 322766 -916023 347922 541726 -594515 -554311 -413504 -881701 -506880 -144667 658945 -503396 791805 314816 -830920 -769486 -200847 845218 468338 -166468 -49854 -287877 -820402 914874 916800 258029 -210000 -296727 702016 -389491 -31529 -52...
output:
500
result:
ok single line: '500'