QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#132503#6570. Who Watches the Watchmen?Sorting#WA 1ms3584kbC++235.9kb2023-07-30 02:05:152023-07-30 02:05:17

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-30 02:05:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2023-07-30 02:05:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

#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;

const int N = 1000 + 3;

bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
    if (A[a] != L) return 0;
    A[a] = -1;
    for (int b : g[a]) if (B[b] == L + 1) {
        B[b] = 0;
        if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
            return btoa[b] = a, 1;
    }
    return 0;
}

int hopcroftKarp(vector<vi>& g, vi& btoa) {
    int res = 0;
    vi A(g.size()), B(btoa.size()), cur, next;
    for (;;) {
        fill(all(A), 0);
        fill(all(B), 0);
        /// Find the starting nodes for BFS (i.e. layer 0).
        cur.clear();
        for (int a : btoa) if(a != -1) A[a] = -1;
        rep(a,0,sz(g)) if(A[a] == 0) cur.push_back(a);
        /// Find all layers using bfs.
        for (int lay = 1;; lay++) {
            bool islast = 0;
            next.clear();
            for (int a : cur) for (int b : g[a]) {
                if (btoa[b] == -1) {
                    B[b] = lay;
                    islast = 1;
                }
                else if (btoa[b] != a && !B[b]) {
                    B[b] = lay;
                    next.push_back(btoa[b]);
                }
            }
            if (islast) break;
            if (next.empty()) return res;
            for (int a : next) A[a] = lay;
            cur.swap(next);
        }
        /// Use DFS to scan for augmenting paths.
        rep(a,0,sz(g))
            res += dfs(a, 0, g, btoa, A, B);
    }
}

template<class T> struct Point3D {
    typedef Point3D P;
    typedef const P& R;
    T x, y, z;
    explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
    bool operator<(R p) const {
        return tie(x, y, z) < tie(p.x, p.y, p.z); }
    bool operator==(R p) const {
        return tie(x, y, z) == tie(p.x, p.y, p.z); }
    P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
    P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
    P operator*(T d) const { return P(x*d, y*d, z*d); }
    P operator/(T d) const { return P(x/d, y/d, z/d); }
    T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
    P cross(R p) const {
        return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
    }
    T dist2() const { return x*x + y*y + z*z; }
    double dist() const { return sqrt((double)dist2()); }
    //Azimuthal angle (longitude) to x-axis in interval [-pi, pi]
    double phi() const { return atan2(y, x); } 
    //Zenith angle (latitude) to the z-axis in interval [0, pi]
    double theta() const { return atan2(sqrt(x*x+y*y),z); }
    P unit() const { return *this/(T)dist(); } //makes dist()=1
    //returns unit vector normal to *this and p
    P normal(P p) const { return cross(p).unit(); }
    //returns point rotated 'angle' radians ccw around axis
    P rotate(double angle, P axis) const {
        double s = sin(angle), c = cos(angle); P u = axis.unit();
        return u*dot(u)*(1-c) + (*this)*c - cross(u)*s;
    }
};

typedef Point3D<ll> P;

int n;
P p[N], v[N];

bool on_line(P a, P b, P c){
    return (b - a).cross(c - a) == P();
}

bool same_direction(P a, P b){
    return a.dot(b) > 0ll;
}

bool b[N][N];
int points_to[N];

vector<vi> adj;
vi btoa;

void solve(){
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            bool ok = true;
            for(int j2 = 0; j2 < n; ++j2){
                if(j2 == i || j2 == j) continue;
                if(on_line(p[i], p[j], p[j2]) && same_direction(p[j2] - p[i], p[j] - p[j2])){
                    ok = false;
                    break;
                }
            }
            b[i][j] = b[j][i] = ok;
        }
    }

    for(int i = 0; i < n; ++i){
        points_to[i] = -1;

        for(int j = 0; j < n; ++j){
            if(i == j) continue;
            if(!b[i][j]) continue;
            if(on_line(p[i], p[j], p[i] + v[i]) && same_direction(v[i], p[j] - p[i])){
                points_to[i] = j;
                break;
            }
        }
    }

    adj.resize(n);
    btoa.resize(n, -1);

    for(int i = 0; i < n; ++i){
        if(points_to[i] != -1){
            adj[i].push_back(points_to[i]);
        }
    }

    cout << n - hopcroftKarp(adj, btoa) << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> p[i].x >> p[i].y >> p[i].z;
        cin >> v[i].x >> v[i].y >> v[i].z;
    }

    if(n == 1){
        cout << "-1\n";
        return 0;
    }

    if(n == 2){
        int ans = 2;
        ans -= on_line(p[0], p[1], p[0] + v[0]) && same_direction(p[1] - p[0], v[0]);
        ans -= on_line(p[1], p[0], p[1] + v[1]) && same_direction(p[0] - p[1], v[1]);
        cout << ans << "\n";
        return 0;
    }

    bool one_line = true;
    for(int i = 2; i < n; ++i)
        one_line &= on_line(p[0], p[1], p[i]);

    if(one_line){
        int cnt_1 = 0, cnt_2 = 0;
        int cnt_other = 0;

        sort(p, p + n);
        for(int i = 0; i < n; ++i){
            if(on_line(p[0], p[1], p[0] + v[i])){
                if(same_direction(p[1] - p[0], v[i]))
                    ++cnt_1;
                else
                    ++cnt_2;
            }
            else{
                ++cnt_other;
            }
        }

        int ans = n - max(cnt_1, cnt_2);
        if(max(cnt_1, cnt_2) == n)
            ++ans;
        if(cnt_other)
            --ans;

        cout << ans << "\n";
        return 0;
    }

    solve();
}
/*
3
0 0 0 0 0 1
0 0 1 0 1 -1
0 0 2 0 0 -1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

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:

2

result:

wrong answer 1st lines differ - expected: '1002', found: '2'