QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795383 | #9804. Guess the Polygon | ucup-team112# | WA | 4ms | 3844kb | C++20 | 16.9kb | 2024-11-30 20:03:47 | 2024-11-30 20:03:48 |
Judging History
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)