QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111867 | #6570. Who Watches the Watchmen? | KhNURE_KIVI | WA | 0ms | 3380kb | C++20 | 15.4kb | 2023-06-09 03:48:53 | 2023-06-09 03:48:57 |
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) {
if (a.first < 0) {
a.first *= -1;
a.second *= -1;
}
if (a.first == 0) {
a.second = abs(a.second);
}
return a.second >= 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];
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] = 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)) {
++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;
}
}
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: 0
Wrong Answer
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 0 0 4 0 0 1 0 0 5 0 0 1 0 0 6 0 0 -1 0 0
output:
1001
result:
wrong answer 1st lines differ - expected: '1002', found: '1001'