QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798119 | #9804. Guess the Polygon | snowysecret | Compile Error | / | / | C++20 | 3.9kb | 2024-12-04 07:14:53 | 2024-12-04 07:14:54 |
Judging History
This is the latest submission verdict.
- [2024-12-04 07:14:54]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-12-04 07:14:53]
- 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 {
int p, q;
Fraction() : p(0), q(1) {}
Fraction(int num, int den) {
assert(den != 0 && "Denominator cannot be zero");
int g = gcd(num, den);
p = num / g;
q = den / g;
if (q < 0) {
p = -p;
q = -q;
}
}
Fraction operator+(Fraction other) const {
int l = q * other.q / gcd(q, other.q);
int num = p * l/q + other.p * l/other.q;
return Fraction(num, l);
}
Fraction operator-(Fraction other) const {
int l = q * other.q / gcd(q, other.q);
int num = p * l/q - other.p * l/other.q;
return Fraction(num, l);
}
Fraction operator*(Fraction other) const {
return Fraction(p * other.p, q * other.q);
}
Fraction operator/(Fraction other) const {
return Fraction(p * other.q, q * other.p);
}
};
Fraction frac(int p, int q) {
return {p, q};
}
Fraction ask(Fraction give) {
assert(give.p * 1. / give.q <= 1000, give.q <= 1000);
cout << "? " << give.p << " " << give.q << endl;
int p, q;
cin >> p >> q;
return frac(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);
Fraction ans = {0, 1};
map<int, int> mp;
map<int, Fraction> len;
for(int i=1; i<=n; i++) mp[p[i].first]++;
vector<int> xs;
for(auto x: mp) xs.push_back(x.first);
for(int i=1; i+1<xs.size(); i++) {
if(mp[xs[i]] == 1) {
len[xs[i]] = ask(frac(xs[i], 1));
}
}
for(int i=1; i<xs.size(); i++) {
Fraction llen, rlen;
Fraction height = frac(xs[i] - xs[i-1], 2);
if(mp[xs[i-1]] == 1) llen = len[xs[i-1]];
else llen = ask(frac(xs[i-1], 1) + frac(1, 1000));
if(mp[xs[i]] == 1) rlen = len[xs[i]];
else rlen = ask(frac(xs[i], 1) - frac(1, 1000));
if(mp[xs[i-1]] == 1 && mp[xs[i]] > 1) {
rlen = llen + (rlen - llen) * (frac(xs[i] - xs[i-1], 1) / (frac(xs[i] - xs[i-1], 1) - frac(1, 1000)));
}
else if(mp[xs[i-1]] > 1 && mp[xs[i]] == 1) {
llen = rlen - (rlen - llen) * (frac(xs[i] - xs[i-1], 1) / (frac(xs[i] - xs[i-1], 1) - frac(1, 1000)));
}
else if(mp[xs[i-1]] > 1 && mp[xs[i]] > 1) {
rlen = llen + (rlen - llen) * (frac(xs[i] - xs[i-1], 1) / (frac(xs[i] - xs[i-1], 1) - frac(1, 500)));
llen = rlen - (rlen - llen) * (frac(xs[i] - xs[i-1], 1) / (frac(xs[i] - xs[i-1], 1) - frac(1, 1000)));
}
Fraction trapezium = (rlen + llen) * height;
ans = ans + trapezium;
}
cout << "! " << ans.p << " " << ans.q << endl;
/*
? 1999 1000
1999 1000
? 2 1
2 1
? 4 1
6 1
? 5999 1000
13999 1200
? 6 1
7 1
*/
}
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
*/
详细
answer.code:65:54: error: macro "assert" passed 2 arguments, but takes just 1 65 | assert(give.p * 1. / give.q <= 1000, give.q <= 1000); | ^ In file included from /usr/include/c++/13/cassert:44, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:106, from answer.code:1: /usr/include/assert.h:92: note: macro "assert" defined here 92 | # define assert(expr) \ | answer.code: In function ‘Fraction ask(Fraction)’: answer.code:65:3: error: ‘assert’ was not declared in this scope 65 | assert(give.p * 1. / give.q <= 1000, give.q <= 1000); | ^~~~~~ answer.code:2:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’? 1 | #include "bits/stdc++.h" +++ |+#include <cassert> 2 | using namespace std;