結果

問題 No.1584 Stones around Circle Pond
ユーザー nok0
提出日時 2021-03-28 13:44:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,849 bytes
コンパイル時間 3,157 ms
コンパイル使用メモリ 205,344 KB
最終ジャッジ日時 2025-01-20 00:11:42
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
static const double EPS = 1e-10;
template <class T>
struct Matrix {
    vector<vector<T> > val;
    Matrix(int n, int m, T x = 0) : val(n, vector<T>(m, x)) {}
    void init(int n, int m, T x = 0) { val.assign(n, vector<T>(m, x)); }
    size_t size() const { return val.size(); }
    inline vector<T>& operator[](int i) { return val[i]; }
};
template <class T>
int GaussJordan(Matrix<T>& A, bool is_extended = false) {
    int m = A.size(), n = A[0].size();
    int rank = 0;
    for(int col = 0; col < n; ++col) {
        // 拡大係数行列の場合は最後の列は掃き出ししない
        if(is_extended && col == n - 1) break;
        // ピボットを探す
        int pivot = -1;
        T ma = EPS;
        for(int row = rank; row < m; ++row) {
            if(abs(A[row][col]) > ma) {
                ma = abs(A[row][col]);
                pivot = row;
            }
        }
        // ピボットがなかったら次の列へ
        if(pivot == -1) continue;
        // まずは行を swap
        swap(A[pivot], A[rank]);
        // ピボットの値を 1 にする
        auto fac = A[rank][col];
        for(int col2 = 0; col2 < n; ++col2) A[rank][col2] /= fac;
        // ピボットのある列の値がすべて 0 になるように掃き出す
        for(int row = 0; row < m; ++row) {
            if(row != rank && abs(A[row][col]) > EPS) {
                auto fac = A[row][col];
                for(int col2 = 0; col2 < n; ++col2) {
                    A[row][col2] -= A[rank][col2] * fac;
                }
            }
        }
        ++rank;
    }
    return rank;
}
template <class T>
vector<T> linear_equation(Matrix<T> A, vector<T> b) {
    // extended
    int m = A.size(), n = A[0].size();
    Matrix<T> M(m, n + 1);
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);
    // check if it has no solution
    vector<T> res;
    for(int row = rank; row < m; ++row)
        if(abs(M[row][n]) > EPS) return res;
    // answer
    res.assign(n, 0);
    for(int i = 0; i < rank; ++i) res[i] = M[i][n];
    return res;
}
using ll = long long;
#define rep(i, x) for(int i = 0; i < (x); i++)
int main() {
    int n, l;
    cin >> n >> l;
    vector d(n, 0ll), b(2 * n, 0ll);
    for(auto& v : d) cin >> v;
    for(auto& v : b) cin >> v;
    auto dist = [&](ll x, ll y) {
        if(x > y) swap(x, y);
        return min(y - x, x + 2 * l - y);
    };
    Matrix<long double> mat(n * 2 + 1, n * 2, 1);
    auto pl = [&](int i) {
        return (i < n ? d[i] : d[i - n] + l);
    };
    rep(i, 2 * n) {
        rep(j, 2 * n) {
            mat[i][j] = dist(pl(i), pl(j));
        }
    }
    ll z = b[0] + b[n];
    if(z % l) {
        puts("No");
        return 0;
    }
    z /= l;
    rep(i, n) {
        if(b[i] + b[n + i] != z * l) {
            puts("No");
            return 0;
        }
    }
    vector<long double> c(2 * n);
    rep(i, 2 * n) c[i] = b[i];
    c.push_back(z);
    auto res = linear_equation(mat, c);
    if(res.empty()) {
        puts("No");
        return 0;
    }
    for(auto& v : res) {
        ll x = round(v);
        if(x < 0 or abs(v - x) > EPS) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0