QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795383#9804. Guess the Polygonucup-team112#WA 4ms3844kbC++2016.9kb2024-11-30 20:03:472024-11-30 20:03:48

Judging History

This is the latest submission verdict.

  • [2024-11-30 20:03:48]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 3844kb
  • [2024-11-30 20:03:47]
  • Submitted

answer


// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define INTERACTIVE

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

namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on

// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on

// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);

// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)

// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}

template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}

template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}

// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}

// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}

// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}

// io functions
void FLUSH() {
    cout << flush;
}

void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}

template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}

template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}

} // namespace io
using namespace io;

// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}

template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}

// yes / no
namespace yesno {

// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}

// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}

// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}

// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}

} // namespace yesno
using namespace yesno;

} // namespace templates
using namespace templates;

template <typename T>
T modinv(T a, T MOD) {
    T b = MOD;
    T u = 1;
    T v = 0;
    while (b > 0) {
        T t = a / b;
        a -= t * b;
        u -= t * v;
        std::swap(a, b);
        std::swap(u, v);
    }
    if (a != 1) return -1;
    if (u < 0) u += MOD;
    return u;
}

struct Fraction {
    long long nume, deno;
    Fraction() : nume(0), deno(1) {}
    Fraction(long long nume) : nume(nume), deno(1) {}
    Fraction(long long nume_, long long deno_) {
        assert(deno_ != 0);
        long long g = std::gcd(nume_, deno_);
        nume        = nume_ / g;
        deno        = deno_ / g;
    }

    Fraction &operator+=(const Fraction &p) {
        long long g = std::gcd(deno, p.deno);
        long long d = deno / g * p.deno;
        long long n = p.deno / g * nume + deno / g * p.nume;
        g           = std::gcd(d, n);
        nume        = n / g;
        deno        = d / g;
        return *this;
    }

    Fraction &operator-=(const Fraction &p) {
        long long g = std::gcd(deno, p.deno);
        long long d = deno / g * p.deno;
        long long n = p.deno / g * nume - deno / g * p.nume;
        g           = std::gcd(d, n);
        nume        = n / g;
        deno        = d / g;
        return *this;
    }

    Fraction &operator*=(const Fraction &p) {
        long long g1 = std::gcd(deno, p.nume);
        long long g2 = std::gcd(nume, p.deno);
        long long d  = (deno / g1) * (p.deno / g2);
        long long n  = (p.nume / g1) * (nume / g2);
        nume         = n;
        deno         = d;
        return *this;
    }

    Fraction &operator/=(const Fraction &p) {
        assert(p.nume != 0);
        *this *= p.inv();
        return *this;
    }

    Fraction operator-() const {
        return Fraction(-nume, deno);
    }

    Fraction &operator++() {
        nume += deno;
        return *this;
    }

    Fraction &operator--() {
        nume -= deno;
        return *this;
    }

    Fraction operator++(int) {
        Fraction result = *this;
        ++*this;
        return result;
    }

    Fraction operator--(int) {
        Fraction result = *this;
        --*this;
        return result;
    }

    friend Fraction operator+(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) += rhs;
    }

    friend Fraction operator-(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) -= rhs;
    }

    friend Fraction operator*(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) *= rhs;
    }

    friend Fraction operator/(const Fraction &lhs, const Fraction &rhs) {
        return Fraction(lhs) /= rhs;
    }

    bool operator==(const Fraction &p) const {
        return (nume == p.nume && deno == p.deno);
    }

    bool operator!=(const Fraction &p) const {
        return (nume != p.nume || deno != p.deno);
    }

    bool operator<(const Fraction &p) const {
        return nume * p.deno < deno * p.nume;
    }

    bool operator<=(const Fraction &p) const {
        return nume * p.deno <= deno * p.nume;
    }

    bool operator>(const Fraction &p) const {
        return nume * p.deno > deno * p.nume;
    }

    bool operator>=(const Fraction &p) const {
        return nume * p.deno >= deno * p.nume;
    }

    long long mod_expression(long long MOD) {
        assert(std::gcd(deno, MOD) == 1);
        return nume * modinv(deno, MOD) % MOD;
    }

    Fraction inv() const {
        return Fraction(deno, nume);
    }

    friend std::ostream &operator<<(std::ostream &os, const Fraction &p) {
        return os << p.nume << '/' << p.deno;
    }

    friend std::istream &operator>>(std::istream &is, Fraction &p) {
        long long y;
        is >> y;
        p = Fraction(y);
        return (is);
    }

    Fraction pow(int64_t k) const {
        Fraction ret(1);
        Fraction y(nume, deno);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }
};

void solve() {
    INT(n);
    VEC(Pll, XY, n);
    sort(all(XY));
    bool same = false;
    fori(i, 1, n) {
        if (XY[i].first == XY[i - 1].first) {
            same = true;
            break;
        }
    }

    if (same) {
        Fraction ans = 0;
        fori(i, 1, n) {
            if (XY[i].first == XY[i - 1].first) continue;
            ll nume = XY[i].first + XY[i - 1].first;
            ll deno = 2;
            if (nume % 2 == 0) {
                nume /= 2;
                deno = 1;
            }
            print("?", nume, deno);
            ll a, b;
            cin >> a >> b;
            ans += Fraction(a, b) * (XY[i].first - XY[i - 1].first);
        }
        print("!", ans.nume, ans.deno);
    } else {
        vec(Pll, D, n);
        D[0]     = {0, 1};
        D[n - 1] = {0, 1};
        fori(i, 1, n - 1) {
            print("?", XY[i].first, 1);
            cin >> D[i].first >> D[i].second;
        }

        Fraction ans = 0;
        fori(i, n - 1) {
            ll dx = XY[i + 1].first - XY[i].first;
            ans += dx *
                   (Fraction(D[i].first, D[i].second) + Fraction(D[i + 1].first, D[i + 1].second)) /
                   2;
        }
        print("!", ans.nume, ans.deno);
    }
}

int main() {
#ifndef INTERACTIVE
    std::cin.tie(0)->sync_with_stdio(0);
#endif
    // std::cout << std::fixed << std::setprecision(12);
    int t;
    t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

//
// // #pragma GCC target("avx2")
// // #pragma GCC optimize("O3")
// // #pragma GCC optimize("unroll-loops")
// #define INTERACTIVE
//
// #include "kyopro-cpp/template.hpp"
//
// #include "misc/fraction.hpp"
//
// void solve() {
//     INT(n);
//     VEC(Pll, XY, n);
//     sort(all(XY));
//     bool same = false;
//     fori(i, 1, n) {
//         if (XY[i].first == XY[i - 1].first) {
//             same = true;
//             break;
//         }
//     }
//
//     if (same) {
//         Fraction ans = 0;
//         fori(i, 1, n) {
//             if (XY[i].first == XY[i - 1].first) continue;
//             ll nume = XY[i].first + XY[i - 1].first;
//             ll deno = 2;
//             if (nume % 2 == 0) {
//                 nume /= 2;
//                 deno = 1;
//             }
//             print("?", nume, deno);
//             ll a, b;
//             cin >> a >> b;
//             ans += Fraction(a, b) * (XY[i].first - XY[i - 1].first);
//         }
//         print("!", ans.nume, ans.deno);
//     } else {
//         vec(Pll, D, n);
//         D[0]     = {0, 1};
//         D[n - 1] = {0, 1};
//         fori(i, 1, n - 1) {
//             print("?", XY[i].first, 1);
//             cin >> D[i].first >> D[i].second;
//         }
//
//         Fraction ans = 0;
//         fori(i, n - 1) {
//             ll dx = XY[i + 1].first - XY[i].first;
//             ans += dx *
//                    (Fraction(D[i].first, D[i].second) + Fraction(D[i + 1].first, D[i +
//                    1].second)) / 2;
//         }
//         print("!", ans.nume, ans.deno);
//     }
// }
//
// int main() {
// #ifndef INTERACTIVE
//     std::cin.tie(0)->sync_with_stdio(0);
// #endif
//     // std::cout << std::fixed << std::setprecision(12);
//     int t;
//     t = 1;
//     std::cin >> t;
//     while (t--) solve();
//     return 0;
// }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3772kb

input:

2
4
3 0
1 3
1 1
0 0
1 1
1 1
3
0 0
999 1000
1000 999
1999 1000

output:

? 1 2
? 2 1
! 3 1
? 999 1
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

9
4
1 1
1 3
3 0
0 0
3 2
1 2
4
0 0
1 3
1 1
3 0
1 2
3 2
4
0 0
3 0
1 2
1 1
1 2
1 2
4
0 0
3 0
1 2
1 1
1 1
1 2
4
0 0
3 0
1 1
1 2
1 2
1 1
3
1000 0
0 0
0 1000
500 1
4
0 0
1000 0
1000 1000
0 1000
1000 1
5
0 1
1000 1000
1000 0
0 1000
1 0
1999 2
1000 1
9
4 1000
3 1
2 1000
3 1000
1 1
2 1
0 0
1 1000
4 0
500 1
1...

output:

? 1 2
? 2 1
! 5 2
? 1 2
? 2 1
! 7 2
? 1 2
? 2 1
! 3 2
? 1 2
? 2 1
! 2 1
? 1 2
? 2 1
! 5 2
? 500 1
! 500000 1
? 500 1
! 1000000 1
? 1 2
? 1001 2
! 1999999 2
? 1 2
? 3 2
? 5 2
? 7 2
! 4003 2

result:

ok correct! (9 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

78
8
951 614
927 614
957 614
957 604
937 614
942 619
951 610
927 604
10 1
25 2
21 2
10 1
7
562 260
602 250
582 255
587 260
602 260
562 250
577 260
10 1
15 2
15 2
10 1
3
454 98
494 68
455 68
117 4
3
526 589
566 559
527 559
117 4
3
854 496
854 466
894 466
15 1
3
797 264
827 254
857 264
10 1
3
719 737
...

output:

? 932 1
? 1879 2
? 1893 2
? 954 1
! 317 1
? 1139 2
? 1159 2
? 1169 2
? 1189 2
! 375 1
? 455 1
! 585 1
? 527 1
! 585 1
? 874 1
! 600 1
? 827 1
! 300 1
? 739 1
! 600 1
? 162 1
! 400 1
? 1489 2
? 1499 2
? 772 1
! 275 1
? 1869 2
? 1879 2
? 1889 2
? 1899 2
? 1909 2
? 1919 2
? 1929 2
? 1939 2
? 1949 2
? 1...

result:

ok correct! (78 test cases)

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 3780kb

input:

34
24
123 815
168 800
133 795
27 827
153 805
28 830
178 780
138 810
78 830
192 772
148 790
88 810
43 825
183 795
103 805
163 785
118 800
93 825
63 835
73 815
58 820
198 790
48 840
108 820
10 3
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
95 6
15 2
15 1
24...

output:

? 28 1
? 43 1
? 48 1
? 58 1
? 63 1
? 73 1
? 78 1
? 88 1
? 93 1
? 103 1
? 108 1
? 118 1
? 123 1
? 133 1
? 138 1
? 148 1
? 153 1
? 163 1
? 168 1
? 178 1
? 183 1
? 192 1
! 1925 1
? 54 1
? 69 1
? 74 1
? 84 1
? 89 1
? 99 1
? 104 1
? 114 1
? 119 1
? 129 1
? 134 1
? 144 1
? 149 1
? 159 1
? 164 1
? 174 1
? ...

result:

wrong answer format  Expected int32, but "692290769659807541" found (test case 27)