QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#675395#7185. Poor StudentsRezhouWA 0ms4028kbC++234.8kb2024-10-25 18:30:152024-10-25 18:30:16

Judging History

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

  • [2024-10-25 18:30:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4028kb
  • [2024-10-25 18:30:15]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef const double* (*p_fun)(const double*, int);
const LL N = 3e3 + 10, M = 2e3 + 10, mod = 1e9 + 7, LLF = 1e15,
null = 0x3f3f3f3f3f3f3f;

template <typename T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T, typename... Args>
bool chmax(T& a, const T& b, const Args&... args) {
    bool updated = chmax(a, b);
    return chmax(a, args...) || updated;
}
template <typename T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T, typename... Args>
bool chmin(T& a, const T& b, const Args&... args) {
    bool updated = chmin(a, b);
    return chmin(a, args...) || updated;
}
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;

public:
    UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (size[x] < size[y]) swap(x, y);
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    bool connected(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }
};
int qmi(int a, int b) {
    int res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}
int sqrt(int x) {
    int l = 0, r = 3e9;  // LLONG_MAX
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (mid * mid > x)
            r = mid - 1;  // 向下取整
        else
            l = mid;
    }
    return r;
}
struct node {
    int op;
    double x, y;
};

double dis(double& bgx, double& bgy, double& edx, double& edy) {
    return sqrt(pow(bgx - edx, 2) + pow(bgy - edy, 2));
}

static inline void solve() {
    int n;
    double t;
    cin >> n >> t;

    double bgx, bgy, edx, edy;
    cin >> bgx >> bgy >> edx >> edy;
    vector<pair<double, double>> v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;

    vector<vector<node>> ans(4);

    double s1 = dis(bgx, bgy, edx, edy);
    ans[1].push_back({ 0,edx,edy });

    node t1 = {}, t2 = {}, t3 = {};
    int posj = 0, posy = 0, mnj = LLF, mny = LLF;
    double x2 = LLF;
    int jl = 0;
    for (int i = 1; i <= n; i++) {
        double disx = abs(v[i].x - bgx), disy = abs(v[i].y - bgy);
        double s2 = min(disx, disy);
        if (s2 < mnj) {
            mnj = s2;
            posj = i;
        }
        double disxf = abs(v[i].x - edx), disyf = abs(v[i].y - edy);
        double s2f = min(disxf, disyf);

        x2 = min(x2, s2 + s2f + t);
        if (x2 == s2 + s2f + t) {
            if (abs(v[posj].first - bgx) < abs(v[posj].y - bgy)) t1 = { 0,v[i].x,bgy };
            else t1 = { 0,bgx,v[i].y };
            if (abs(v[posy].x - edx) < abs(v[posy].y - edy)) t2 = { i,v[i].x,edy };
            else t2 = { i,edx,v[i].y };

            t3 = { 0,edx,edy };
        }
        if (s2f < mny) {
            mny = s2f;
            posy = i;
        }
    }

    vector<node> vv;
    double s3 = 0;
    s3 += mnj + mny + t * 2;

    if (abs(v[posj].first - bgx) < abs(v[posj].y - bgy)) vv.push_back({ 0,v[posj].x,bgy });
    else  vv.push_back({ 0,bgx,v[posj].y });

    vv.push_back({ posj,v[posj].x,v[posy].y });
    if (abs(v[posy].x - edx) < abs(v[posy].y - edy)) vv.push_back({ posy,v[posy].x,edy });
    else vv.push_back({ 0,edx,v[posj].y });

    if (s1 < x2 && s1 < s3) {
        cout << s1 << endl;
        cout << ans[1].size() << endl;
        for (auto& [x, y, z] : ans[1]) cout << x << ' ' << y << " " << z << endl;
    }
    else if (x2 < s3) {
        cout << x2 << endl;
        cout << 3 << endl;
        auto [x, y, z] = t1;
        cout << x << " " << y << " " << z << endl;
        cout << t2.op << " " << t2.first << " " << t2.second << endl;
        cout << 0 << " " << edx << " " << edy << endl;
    }
    else {
        cout << s3 << endl;
        cout << vv.size() << endl;
        for (auto& [x, y, z] : vv)
            cout << x << " " << y << " " << z << endl;
    }

}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << unitbuf;
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4028kb

input:

6 2
1 2
1 3
1 4
1 5
1 6
1 7
3 4

output:

1
1
0 1 3

result:

wrong answer expected '12', found '1'