QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794959 | #9804. Guess the Polygon | ucup-team5243# | WA | 7ms | 3732kb | C++23 | 16.3kb | 2024-11-30 17:07:49 | 2024-11-30 17:07:52 |
Judging History
answer
//line 1 "answer.cpp"
#if !__INCLUDE_LEVEL__
#include __FILE__
int solve() {
ll n; input(n);
vl x(n), y(n);
rep(i, n) input(x[i], y[i]);
auto query = [&] (Frac f) -> Frac {
f.reduce();
print("?", f.num, f.den);
cout.flush();
ll r,s; input(r, s);
return Frac(r, s);
};
auto answer = [&] (Frac f) {
f.reduce();
print("!", f.num, f.den);
cout.flush();
};
vl c = x;
uniq(c);
vector<Frac> fx(sz(c));
rep(i, sz(c)) fx[i] = Frac(c[i], 1);
vl cnt(sz(c), 0);
rep(i, n) {
ll p = lower_bound(all(c), x[i]) - c.begin();
cnt[p]++;
}
vector<pair<Frac,Frac>> qa(sz(c));
vector<bool> mv(sz(c), false);
Frac diff = Frac(1, 1000);
debug(c, cnt);
if (cnt[0] > 1) {
mv[0] = true;
qa[0].second = query(fx[0] + diff);
} else {
qa[0].second = Frac(0, 1);
}
if (cnt[sz(c)-1] > 1) {
mv[sz(c)-1] = true;
qa[sz(c)-1].first = query(fx[sz(c)-1] - diff);
} else {
qa[sz(c)-1].first = Frac(0, 1);
}
rep(i, 1, sz(c)-1) {
debug(i);
if (cnt[i] == 1) {
Frac ans = query(fx[i]);
qa[i].first = ans;
qa[i].second = ans;
} else {
mv[i] = true;
qa[i].first = query(fx[i] - diff);
qa[i].second = query(fx[i] + diff);
}
}
Frac ans = Frac(0);
rep(i, sz(c)-1) {
auto f1 = qa[i].second;
auto f2 = qa[i+1].first;
Frac dist = fx[i+1] - fx[i];
if (mv[i]) dist = dist - diff;
if (mv[i+1]) dist = dist - diff;
debug(dist);
if (mv[i]) {
f1 = f1 + (f1 - f2) / dist * diff;
dist = dist + diff;
}
if (mv[i+1]) {
f2 = f2 + (f2 - f1) / dist * diff;
dist = dist + diff;
}
debug(f1, f2, dist);
ans = ans + ((f1 + f2) * dist) / Frac(2);
}
answer(ans);
return 0;
}
int main() {
ll t; input(t);
rep(t) solve();
}
#else
//line 2 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/std.hpp"
#include <bits/stdc++.h>
#ifndef LOCAL_TEST
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // LOCAL_TEST
using namespace std;
// 型名の短縮
using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using vs = vector<string>; using vvs = vector<vector<string>>; using vvvs = vector<vector<vector<string>>>;
template<typename T> vector<vector<T>> vv(int h, int w, T val = T()) { return vector(h, vector<T>(w, val)); }
template<typename T> vector<vector<vector<T>>> vvv(int h1, int h2, int h3, T val = T()) { return vector(h1, vector(h2, vector<T>(h3, val))); }
template<typename T> vector<vector<vector<vector<T>>>> vvvv(int h1, int h2, int h3, int h4, T val = T()) { return vector(h1, vector(h2, vector(h3, vector<T>(h4, val)))); }
template <class T> using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;
// 定数の定義
constexpr double PI = 3.14159265358979323;
constexpr int INF = 100100111; constexpr ll INFL = 3300300300300300491LL;
float EPS = 1e-8; double EPSL = 1e-16;
template<typename T> bool eq(const T x, const T y) { return x == y; }
template<> bool eq<double>(const double x, const double y) { return abs(x - y) < EPSL; }
template<> bool eq<float>(const float x, const float y) { return abs(x - y) < EPS; }
template<typename T> bool neq(const T x, const T y) { return !(eq<T>(x, y)); }
template<typename T> bool ge(const T x, const T y) { return (eq<T>(x, y) || (x > y)); }
template<typename T> bool le(const T x, const T y) { return (eq<T>(x, y) || (x < y)); }
template<typename T> bool gt(const T x, const T y) { return !(le<T>(x, y)); }
template<typename T> bool lt(const T x, const T y) { return !(ge<T>(x, y)); }
constexpr int MODINT998244353 = 998244353;
constexpr int MODINT1000000007 = 1000000007;
// 入出力高速化
struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } nyan;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((ll)(x).size())
#define rep1(n) for(ll dummy_iter = 0LL; dummy_iter < n; ++dummy_iter) // 0 から n-1 まで昇順
#define rep2(i, n) for(ll i = 0LL, i##_counter = 0LL; i##_counter < ll(n); ++(i##_counter), (i) = i##_counter) // 0 から n-1 まで昇順
#define rep3(i, s, t) for(ll i = ll(s), i##_counter = ll(s); i##_counter < ll(t); ++(i##_counter), (i) = (i##_counter)) // s から t まで昇順
#define rep4(i, s, t, step) for(ll i##_counter = step > 0 ? ll(s) : -ll(s), i##_end = step > 0 ? ll(t) : -ll(t), i##_step = abs(step), i = ll(s); i##_counter < i##_end; i##_counter += i##_step, i = step > 0 ? i##_counter : -i##_counter) // s から t まで stepずつ
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define repe(a, v) for(auto& a : (v)) // v の全要素(変更可能)
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define sdiv(n, m) (((n) - smod(n, m)) / (m)) // 非負div
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
int Yes(bool b=true) { cout << (b ? "Yes\n" : "No\n"); return 0; };
int YES(bool b=true) { cout << (b ? "YES\n" : "NO\n"); return 0; };
int No(bool b=true) {return Yes(!b);};
int NO(bool b=true) {return YES(!b);};
template<typename T, size_t N> T max(array<T, N>& a) { return *max_element(all(a)); };
template<typename T, size_t N> T min(array<T, N>& a) { return *min_element(all(a)); };
template<typename T> T max(vector<T>& a) { return *max_element(all(a)); };
template<typename T> T min(vector<T>& a) { return *min_element(all(a)); };
template<typename T> vector<T> accum(const vector<T>& a) { vector<T> rev(sz(a)+1, 0); rep(i, sz(a)) rev[i+1] = rev[i] + a[i]; return rev; };
template<typename T> vector<T> vec_slice(const vector<T>& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> T sum(vector<T>& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };
template<typename T> bool in_range(const T& val, const T& s, const T& t) { return s <= val && val < t; };
template <class T> inline vector<T>& operator--(vector<T>& v) { repe(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repe(x, v) ++x; return v; }
// modでのpow
ll powm(ll a, ll n, ll mod=INFL) {
ll res = 1;
while (n > 0) {
if (n & 1) res = (res * a) % mod;
if (n > 1) a = (a * a) % mod;
n >>= 1;
}
return res;
}
// 整数Sqrt
ll sqrtll(ll x) {
assert(x >= 0);
ll rev = sqrt(x);
while(rev * rev > x) --rev;
while((rev+1) * (rev+1)<=x) ++rev;
return rev;
}
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す)
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す)
int digit(ll x, int d=10) { int rev=0; while (x > 0) { rev++; x /= d;}; return rev; } // xのd進数桁数
/**
* @brief std.hpp
* @docs docs/std/std.md
*/
//line 3 "/home/seekworser/.cpp_lib/competitive_library/competitive/math/fraction.hpp"
struct Frac {
ll num;
ll den;
Frac (ll _num, ll _den, bool reduce = true) : num(_num), den(_den) {
if (reduce) (*this).reduce();
}
Frac (ll _num) : Frac(_num, 1) {}
Frac () : num(0), den(1) {}
static ll redcue_limit;
Frac inv() const { return Frac((*this).den, (*this).num); }
Frac &operator+=(const Frac &x) {
(*this).num = (*this).num * x.den + x.num * (*this).den;
(*this).den = (*this).den * x.den;
if ((*this).den > redcue_limit || (*this).num > redcue_limit) (*this).reduce();
return (*this);
}
Frac &operator-=(const Frac &x) {
(*this).num = (*this).num * x.den - x.num * (*this).den;
(*this).den = (*this).den * x.den;
if ((*this).den > redcue_limit || (*this).num > redcue_limit) (*this).reduce();
return (*this);
}
Frac &operator*=(const Frac &x) {
(*this).num = (*this).num * x.num;
(*this).den = (*this).den * x.den;
if ((*this).den > redcue_limit || (*this).num > redcue_limit) (*this).reduce();
return (*this);
}
Frac &operator/=(const Frac &x) {
(*this) *= x.inv();
if ((*this).den > redcue_limit || (*this).num > redcue_limit) (*this).reduce();
return (*this);
}
Frac operator+(const Frac &x) const { return (Frac(*this) += x); }
Frac operator-(const Frac &x) const { return (Frac(*this) -= x); }
Frac operator*(const Frac &x) const { return (Frac(*this) *= x); }
Frac operator/(const Frac &x) const { return (Frac(*this) /= x); }
Frac operator+() const { return *this; }
Frac operator-() const { Frac x(-(*this).num, (*this).den); return x; }
friend bool operator==(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den == lhs.den * rhs.num;
}
friend bool operator!=(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den != lhs.den * rhs.num;
}
friend bool operator>=(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den >= lhs.den * rhs.num;
}
friend bool operator<=(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den <= lhs.den * rhs.num;
}
friend bool operator>(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den > lhs.den * rhs.num;
}
friend bool operator<(const Frac& lhs, const Frac& rhs) {
return lhs.num * rhs.den < lhs.den * rhs.num;
}
double val() const {return (double)((*this).num) / (double)((*this).den); }
friend ostream& operator<<(ostream& os, const Frac &x) { os << x.val(); return os; }
void reduce() {
assert((*this).den != 0 || (*this).num != 0);
if ((*this).den == 0) { (*this).num = 1; return; }
if ((*this).num == 0) { (*this).den = 1; return; }
ll g = gcd((*this).num, (*this).den);
(*this).num /= g;
(*this).den /= g;
if ((*this).den < 0) {
(*this).num *= -1;
(*this).den *= -1;
}
return;
}
};
ll Frac::redcue_limit = 1000000000;
Frac pow(const Frac &a, ll n) {
Frac res(1); Frac cur(a);
while (n > 0) {
if (n & 1) res *= cur;
cur *= cur;
n >>= 1;
}
return res;
}
Frac abs(const Frac &f) {
Frac rev(f);
if (rev.den * rev.num < 0) return -rev;
return rev;
}
/**
* @brief fraction.hpp
* @docs docs/math/fraction.md
*/
//line 3 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/io.hpp"
// 演算子オーバーロード(プロトタイプ宣言)
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p);
template <class T> inline istream& operator>>(istream& is, vector<T>& v);
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repe(x, v) is >> x; return is; }
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << " " << p.second; return os; }
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { os << v.at(i); if (i != sz(v) - 1) os << " "; } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st) { ll cnt = 0; for (auto &e : st) { os << e << (++cnt != (int)st.size() ? " " : ""); } return os; }
template <typename T> ostream &operator<<(ostream &os, queue<T> q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; }
template <typename T> ostream &operator<<(ostream &os, stack<T> st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; }
template <typename T> int print_sep_end(string sep, string end, const T& val) { (void)sep; cout << val << end; return 0; };
template <typename T1, typename... T2> int print_sep_end(string sep, string end, const T1 &val, const T2 &...remain) {
cout << val << sep;
print_sep_end(sep, end, remain...);
return 0;
};
template <typename... T> int print(const T &...args) { print_sep_end(" ", "\n", args...); return 0; };
template <typename... T> void flush() { cout << flush; };
template <typename... T> int print_and_flush(const T &...args) { print(args...); flush(); return 0; };
#define debug(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__) // debug print
template <typename T> void input(T &a) { cin >> a; };
template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };
#ifdef LOCAL_TEST
template <typename T> void debug_func(int i, const T name) { (void)i; (void)name; cerr << endl; }
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
int scope = 0;
for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
cerr << name[i];
if (name[i] == '(' || name[i] == '{') scope++;
if (name[i] == ')' || name[i] == '}') scope--;
}
cerr << ":" << a << " ";
debug_func(i + 1, name, b...);
}
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, T2 &a, T3 &...b) {
int scope = 0;
for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
cerr << name[i];
if (name[i] == '(' || name[i] == '{') scope++;
if (name[i] == ')' || name[i] == '}') scope--;
}
cerr << ":" << a << " ";
debug_func(i + 1, name, b...);
}
#endif
#ifndef LOCAL_TEST
template <typename... T>
void debug_func(T &...) {}
template <typename... T>
void debug_func(const T &...) {}
#endif
/**
* @brief io.hpp
* @docs docs/std/io.md
*/
//line 86 "answer.cpp"
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
2 4 3 0 1 3 1 1 0 0 999 500 1999 1000 3 0 0 999 1000 1000 999 1999 1000
output:
? 999 1000 ? 1001 1000 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
9 4 1 1 1 3 3 0 0 0 2997 1000 1999 2000 4 0 0 1 3 1 1 3 0 999 1000 5997 2000 4 0 0 3 0 1 2 1 1 999 1000 1999 2000 4 0 0 3 0 1 2 1 1 999 500 1999 2000 4 0 0 3 0 1 1 1 2 999 1000 1999 1000 3 1000 0 0 0 0 1000 999999 1000 4 0 0 1000 0 1000 1000 0 1000 1000 1 1000 1 5 0 1 1000 1000 1000 0 0 1000 1 0 999...
output:
? 999 1000 ? 1001 1000 ! 5 2 ? 999 1000 ? 1001 1000 ! 7 2 ? 999 1000 ? 1001 1000 ! 3 2 ? 999 1000 ? 1001 1000 ! 2 1 ? 999 1000 ? 1001 1000 ! 5 2 ? 1 1000 ! 500000 1 ? 1 1000 ? 999999 1000 ! 1000000 1 ? 1 1000 ? 999999 1000 ? 1 1 ! 1999999 2 ? 3999 1000 ? 999 1000 ? 1001 1000 ? 1999 1000 ? 2001 1000 ...
result:
ok correct! (9 test cases)
Test #3:
score: 0
Accepted
time: 7ms
memory: 3632kb
input:
78 8 951 614 927 614 957 614 957 604 937 614 942 619 951 610 927 604 10 1 10 1 10 1 15 1 6001 1000 10 1 7 562 260 602 250 582 255 587 260 602 260 562 250 577 260 10 1 10 1 10 1 5 1 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 119997 4000 3 797 264 827 2...
output:
? 927001 1000 ? 956999 1000 ? 937 1 ? 942 1 ? 950999 1000 ? 951001 1000 ! 317 1 ? 562001 1000 ? 601999 1000 ? 577 1 ? 582 1 ? 587 1 ! 375 1 ? 455 1 ! 585 1 ? 527 1 ! 585 1 ? 854001 1000 ! 600 1 ? 827 1 ! 300 1 ? 719001 1000 ! 600 1 ? 162 1 ! 400 1 ? 742001 1000 ? 791999 1000 ? 746999 1000 ? 747001 1...
result:
ok correct! (78 test cases)
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 3732kb
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 "-64968253399438835" found (test case 27)