QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131322#6570. Who Watches the Watchmen?installbWA 1731ms11884kbC++146.6kb2023-07-26 22:14:452023-07-26 22:14:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-26 22:14:48]
  • 评测
  • 测评结果:WA
  • 用时:1731ms
  • 内存:11884kb
  • [2023-07-26 22:14:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2005;
const int M = 1000005;

struct point{
    int x,y,z; int id;
    point (int _x = 0,int _y = 0,int _z = 0) : x(_x), y(_y), z(_z) {}
}p[N],d[N],sp[N],q[N];

int n;

bool cmp(point p1,point p2){
    if(p1.x != p2.x) return p1.x < p2.x;
    if(p1.y != p2.y) return p1.y < p2.y;
    return p1.z < p2.z;
}

point simpl(const point &p){
    int x = abs(__gcd(p.x,__gcd(p.y,p.z)));
    return point(p.x / x,p.y / x,p.z / x);
}

point operator - (const point &p1,const point &p2){
    return point(p1.x - p2.x,p1.y - p2.y,p1.z - p2.z);
}

point operator + (const point &p1,const point &p2){
    return point(p1.x + p2.x,p1.y + p2.y,p1.z + p2.z);
}

point det(const point &p1,const point &p2){
    return point(p1.y * p2.z - p1.z * p2.y,p1.z * p2.x - p1.x * p2.z,p1.x * p2.y - p1.y * p2.x);
}

ll dot(const point &p1,const point &p2){
    return 1ll * p1.x * p2.x + 1ll * p1.y * p2.y + 1ll * p1.z * p2.z;
}

int len(const point &p){
    return abs(p.x) + abs(p.y) + abs(p.z);
}

bool operator == (const point &p1,const point &p2){
    return p1.x == p2.x && p1.y == p2.y && p1.z == p2.z;
}

bool operator != (const point &p1,const point &p2){
    return p1.x != p2.x || p1.y != p2.y || p1.z != p2.z;
}

bool eq(const point &p1,const point &p2){
    return simpl(p1) == simpl(p2) || simpl(p1) == point(0,0,0) - simpl(p2);
} // parallel

bool eq2(const point &p1,const point &p2){
    return simpl(p1) == simpl(p2);
} // same direction

void input(point &p){
    cin >> p.x >> p.y >> p.z;
}

int ec = 1,to[M << 1],nxt[M << 1],cap[M << 1],w[M << 1];
int hed[N];
void add_edge(int f,int t,int c,int d){
    ++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; cap[ec] = c; w[ec] = d;
    ++ ec; to[ec] = f; nxt[ec] = hed[t]; hed[t] = ec; cap[ec] = 0; w[ec] = -d;
}

int dis[N],inq[N],flw[N],pre[N],prv[N];

const int INF = 0x3f3f3f3f;

int spfa(int s,int t){
    for(int i = 1;i <= t;i ++){
        dis[i] = INF; inq[i] = 0; flw[i] = 0;
    }
    prv[t] = -1;
    queue <int> q;
    q.push(s); inq[s] = 1; dis[s] = 0; flw[s] = INF;
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = 0;
        for(int i = hed[u];i;i = nxt[i]){
            int v = to[i];
            if(dis[v] > dis[u] + w[i] && cap[i]){
                dis[v] = dis[u] + w[i];
                prv[v] = u;
                pre[v] = i;
                flw[v] = min(flw[u],cap[i]);
                if(!inq[v]){
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    return prv[t] != -1;
}

int mcf = 0,mxf = 0;
void mcmf(int s,int t){
    while(spfa(s,t)){
        mxf += flw[t];
        mcf += flw[t] * dis[t];
        int now = t;
        while(now != s){
            cap[pre[now]] -= flw[t];
            cap[pre[now] ^ 1] += flw[t];
            now = prv[now];
        }
    }
}

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i ++){
        input(p[i]);
        input(d[i]);
        p[i].id = i;
    }
    if(n == 1){
        cout << -1 << '\n';
        return;
    }

    int S = n + n + 1;
    int T = S + 1;
    for(int i = 1;i <= n;i ++){
        point di = simpl(d[i]);
        for(int j = 1;j <= n;j ++) if(j != i) sp[j] = simpl(p[j] - p[i]);
        for(int j = 1;j <= n;j ++){
            if(i == j) continue;
            int fl = 0;
            for(int k = 1;k <= n;k ++){
                if(k == i || k == j) continue;
                if(sp[k] == sp[j] && len(p[k] - p[i]) < len(p[j] - p[i])){
                    fl = 1; break;
                }
            }
            if(!fl){
                if(sp[j] == di) add_edge(i,j + n,1,0);
                else add_edge(i,j + n,1,1);
            }
        }
        add_edge(S,i,1,0);
        add_edge(i + n,T,1,0);
    }
    mcmf(S,T);
    if(mxf == n){
        cout << mcf << '\n';
        return;
    }

    int del = 0;
    for(int id = 1;id <= n;id ++){
        int qc = 0;
        for(int i = 1;i <= n;i ++){
            if(i == id) continue;
            q[++ qc] = p[i];
        }
        sort(q + 1,q + 1 + qc,cmp);

        vector <int> tor(qc + 2),fromr(qc + 2),pre(qc + 2),suf(qc + 2);
        tor[0] = fromr[0] = 0;
        for(int i = 1;i < qc;i ++){
            tor[i] = tor[i - 1];
            fromr[i] = fromr[i - 1];
            if(eq2(d[q[i].id],q[i + 1] - q[i])) tor[i] ++;
            if(eq2(d[q[i + 1].id],q[i] - q[i + 1])) fromr[i] ++;
        }
        pre[0] = suf[qc + 1] = 0;
        for(int i = 2;i <= qc;i += 2){
            pre[i] = pre[i - 2];
            if(eq2(d[q[i - 1].id],q[i] - q[i - 1])) pre[i] ++;
            if(eq2(d[q[i].id],q[i - 1] - q[i])) pre[i] ++;
        }
        for(int i = qc - 1;i >= 1;i -= 2){
            suf[i] = suf[i + 2];
            if(eq2(d[q[i].id],q[i + 1] - q[i])) suf[i] ++;
            if(eq2(d[q[i + 1].id],q[i] - q[i + 1])) suf[i] ++;
        }

        for(int l = 1;l <= qc;l += 2){
            for(int r = qc;r >= l;r -= 2){
                int cur = 0,lrs = 0;
                lrs = pre[l - 1] + suf[r + 1];
                // id -> l -> r -> id, d[id], d[r], l->r(q[r] - q[l]) froms a triangle
                cur = tor[r - 1] - tor[l - 1];
                if(l != r && eq(d[id],q[r] - q[l]) && eq(d[q[r].id],q[r] - q[l])) cur += 0;
                else if((l != r && !eq(q[r] - q[l],d[q[r].id]) && !eq(q[r] - q[l],d[id]) && !eq(d[q[r].id],d[id]) && dot(det(q[r] - q[l],d[q[r].id]),d[id]) == 0) || (l == r && simpl(point(0,0,0) - d[q[l].id]) == simpl(d[id]))) cur += 2;
                else cur ++;
                del = max(del,cur + lrs);
                // id -> r -> l -> id
                cur = fromr[r - 1] - fromr[l - 1];
                if(l != r && eq(d[id],q[r] - q[l]) && eq(d[q[l].id],q[r] - q[l])) cur += 0;
                else if((l != r && !eq(q[r] - q[l],d[q[l].id]) && !eq(q[r] - q[l],d[id]) && !eq(d[q[l].id],d[id]) && dot(det(q[r] - q[l],d[q[l].id]),d[id]) == 0) || (l == r && simpl(point(0,0,0) - d[q[l].id]) == simpl(d[id]))) cur += 2;
                else cur ++;
                del = max(del,cur + lrs);
                // cout << id << ' ' << l << ' ' << r << ' ' << cur + lrs << endl;
                // cout << d[q[l].id].x << ',' << d[q[l].id].y << ' ' << d[id].x << ',' << d[id].y << '(' << eq(d[q[l].id],d[id]) << ' ' << eq(d[q[r].id],d[id]) << ')' << tor[r - 1] - tor[l - 1] << ' ' << fromr[r - 1] - fromr[l - 1] << '\n';
            }
        }
    }
    cout << 1000 + n - del << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9776kb

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: 9768kb

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: 0ms
memory: 9772kb

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: 2ms
memory: 9832kb

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: 11808kb

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: 9784kb

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: 2ms
memory: 9760kb

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: 1ms
memory: 3612kb

input:

1
0 0 0 3 1 4

output:

-1

result:

ok single line: '-1'

Test #9:

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

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: 77ms
memory: 9844kb

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: 82ms
memory: 9820kb

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: 89ms
memory: 9876kb

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: 9896kb

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: 9836kb

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: 2ms
memory: 9840kb

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: 2ms
memory: 9848kb

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: 1129ms
memory: 9808kb

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: 1473ms
memory: 11844kb

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: 1731ms
memory: 9852kb

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: 9828kb

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: 9828kb

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: 9896kb

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: 9776kb

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: 1ms
memory: 11884kb

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: 9776kb

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: -100
Wrong Answer
time: 0ms
memory: 9892kb

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:

1000

result:

wrong answer 1st lines differ - expected: '1001', found: '1000'