Submission #50429200

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;
typedef double realType;

std::mt19937 engine(std::chrono::steady_clock::now().time_since_epoch().count() ^ std::random_device()() ^ (size_t) (std::make_unique<char>().get()));

realType Random() {
    return (realType) engine() / engine.max();
}

valueType Random(valueType n) {
    return engine() % n;
}

valueType Random(valueType l, valueType r) {
    return l + Random(r - l + 1);
}

valueType Inverse(valueType N, ValueVector const &P) { // Computes the reverse logarithm of a permutation of order N
    __gnu_pbds::tree<valueType, __gnu_pbds::null_type, std::greater<>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> T;

    valueType result = 0;

    for (valueType i = 0; i < N; ++i) {
        result += (valueType) T.order_of_key(P[i]);

        T.insert(P[i]);
    }

    return result;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    PairVector Limit(N * (N - 1) / 2);

    for (auto &[u, v] : Limit)
        std::cin >> u >> v;

    ValueMatrix Ans(N + 1, ValueVector(N, 0));

    constexpr valueType V = 1e8;

    for (auto &v : Ans)
        for (auto &x : v)
            x = Random(0, V);

    auto Calc = [&]() -> valueType {
        PairVector P;
        P.reserve(N * (N - 1) / 2);

        for (valueType i = 0; i < Limit.size(); ++i) {
            auto const &[u, v] = Limit[i];

            valueType sum = 0;

            for (valueType j = 0; j < N; ++j)
                sum += (Ans[u][j] - Ans[v][j]) * (Ans[u][j] - Ans[v][j]);

            P.emplace_back(sum, i);
        }

        std::sort(P.begin(), P.end());

        for (valueType i = 1; i < P.size(); ++i)
            if (P[i].first == P[i - 1].first)
                return 1e8;

        ValueVector Q(P.size());

        for (valueType i = 0; i < P.size(); ++i)
            Q[i] = P[i].second;

        return Inverse(N * (N - 1) / 2, Q);
    };

    valueType ans = Calc();

    while (ans != 0) {
        realType T = 1e5;

        while (T > 1E-1) {
            valueType const i = Random(1, N), j = Random(0, N - 1);

            valueType const Prev = Ans[i][j];

            Ans[i][j] = Random(0, V);

            valueType const now = Calc();

            valueType const delta = now - ans;

            if (delta < 0) {
                ans = now;
            } else {
                Ans[i][j] = Prev;
            }

            T *= 0.99;
        }
    }

    for (valueType i = 1; i <= N; ++i) {
        for (auto const &x : Ans[i])
            std::cout << x << ' ';

        std::cout << std::endl;
    }
}

Submission Info

Compile Error

Main.cpp: In lambda function:
Main.cpp:77:33: warning: comparison of integer expressions of different signedness: ‘valueType’ {aka ‘long long int’} and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   77 |         for (valueType i = 0; i < Limit.size(); ++i) {
      |                               ~~^~~~~~~~~~~~~~
Main.cpp:90:33: warning: comparison of integer expressions of different signedness: ‘valueType’ {aka ‘long long int’} and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   90 |         for (valueType i = 1; i < P.size(); ++i)
      |                               ~~^~~~~~~~~~
Main.cpp:96:33: warning: comparison of integer expressions of different signedness: ‘valueType’ {aka ‘long long int’} and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   96 |         for (valueType i = 0; i < P.size(); ++i)
      |                               ~~^~~~~~~~~~

Judge Result