QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#797466 | #9804. Guess the Polygon | snowysecret | Compile Error | / | / | C++14 | 2.9kb | 2024-12-03 04:00:04 | 2024-12-03 04:00:05 |
Judging History
This is the latest submission verdict.
- [2024-12-03 04:00:05]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-12-03 04:00:04]
- Submitted
answer
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 4e5 + 10, MOD = 1e9 + 7, HASHMOD = 1734232211;
int fac[MAXN], invfac[MAXN];
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) { return uniform_int_distribution<int>(x, y)(rng); }
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) { return bm(b, MOD-2); }
vector<int> prefix_function(vector<int> t) {
int n = t.size(); vector<int> lps(n, 0);
for(int i=1; i<n; i++) {
int j = lps[i-1]; while(j > 0 && t[i] != t[j]) j = lps[j-1];
lps[i] = (t[i] == t[j] ? j+1 : 0);
} return lps;
}
int nCr(int n, int r) {
return (((fac[n] * invfac[r]) % MOD) * invfac[n-r]) % MOD;
}
void precomp() {
for(int i=0; i<MAXN; i++) fac[i] = (i ? (fac[i-1] * i) % MOD : 1);
invfac[MAXN - 1] = inv(fac[MAXN - 1]);
for(int i=MAXN-2; i>=0; i--) invfac[i] = (invfac[i+1] * (i+1)) % MOD;
}
struct Fraction {
__int128 gcdd(__int128 x, __int128 y) {
if(x == 0) return y;
if(y == 0) return x;
if(x < y) return gcdd(x, y % x);
return gcdd(y, x % y);
}
int p, q;
Fraction operator*(Fraction other) {
__int128 num = p, den = q;
num *= other.p, den *= other.q;
__int128 g = gcdd(num, den);
num /= g, den /= g;
int n1 = num, n2 = den;
Fraction product = {n1, n2};
return product;
}
Fraction operator+(Fraction other) {
__int128 l = q * other.q / gcd(q, other.q);
__int128 num = p * l/q + other.p * l/other.q;
__int128 g = gcdd(l, num);
l /= g, num /= g;
int n1 = num, n2 = l;
Fraction sum = {n1, n2};
return sum;
}
};
Fraction frac(int p, int q) {
return {p, q};
}
void solve(int tc) {
int n;
cin >> n;
pair<int, int> p[n+1];
for(int i=1; i<=n; i++) {
cin >> p[i].first >> p[i].second;
}
sort(p + 1, p + n + 1);
vector<pair<int, Fraction>> v;
if(p[1].first != p[2].first) {
v.push_back({p[1].first, {0, 1}});
}
for(int i=2; i<=n-1; i++) {
if(p[i].first == p[i-1].first) continue;
cout << "? " << p[i].first << " 1" << endl;
int pp, q;
cin >> pp >> q;
v.push_back({p[i].first, {pp, q}});
}
if(p[n-1].first != p[n].first) {
v.push_back({p[n].first, {0, 1}});
}
Fraction ans = {0, 1};
for(int i=1; i<v.size(); i++) {
Fraction base = v[i-1].second + v[i].second;
int height = v[i].first - v[i-1].first;
Fraction res1 = base * frac(height, 2);
ans = ans + res1;
}
cout << "! " << ans.p << " " << ans.q << "\n";
}
int32_t main() {
precomp();
//ios::sync_with_stdio(0); cin.tie(0);
int t = 1; cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
/*
g++ code.cpp -std=c++17 -O2 -o code
./code < input.txt
*/
Details
answer.code: In member function ‘Fraction Fraction::operator+(Fraction)’: answer.code:49:32: error: ‘gcd’ was not declared in this scope; did you mean ‘gcdd’? 49 | __int128 l = q * other.q / gcd(q, other.q); | ^~~ | gcdd