QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794988 | #9804. Guess the Polygon | ucup-team3670# | RE | 1ms | 3608kb | C++20 | 1.8kb | 2024-11-30 17:21:00 | 2024-11-30 17:21:01 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
using namespace std;
const long long MOD = (long long)(1e18) + 3;
long long add(long long a, long long b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
long long mul(long long a, long long b){
return a * __int128(b) % MOD;
}
long long binpow(long long a, long long b){
long long res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
struct point{
int x, y;
};
long long get(string s){
long long res = 0;
for (char c : s)
res = add(mul(res, 10), c - '0');
return res;
}
void solve(){
int n;
cin >> n;
vector<point> a(n);
forn(i, n) cin >> a[i].x >> a[i].y;
sort(a.begin(), a.end(), [](const point &a, const point &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<pair<long long, long long>> inter(n, {0, 1});
for (int i = 1; i < n - 1; ++i){
cout << "? " << a[i].x << " " << 1 << endl;
string p, q;
cin >> p >> q;
inter[i] = {get(p), get(q)};
assert(inter[i].second != 0);
}
if (a[0].x == a[1].x) inter[0] = inter[1];
if (a[n - 1].x == a[n - 2].x) inter[n - 1] = inter[n - 2];
long long ans = 0;
forn(i, n - 1){
long long s1 = mul(inter[i].first, binpow(inter[i].second, MOD - 2));
long long s2 = mul(inter[i + 1].first, binpow(inter[i + 1].second, MOD - 2));
ans = add(ans, mul(add(s1, s2), a[i + 1].x - a[i].x));
}
//for (auto it : inter)
// cerr << ". " << it.first << " " << it.second << endl;
int g = __gcd(ans, 2ll);
cout << "! " << ans / g << " " << 2 / g << endl;
}
int main(){
int tc;
cin >> tc;
while (tc--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
2 4 3 0 1 3 1 1 0 0 2 1 2 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 1 ? 1 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: -100
Runtime Error
input:
9 4 1 1 1 3 3 0 0 0 3 1 3 1
output:
? 1 1 ? 1 1 ! 9 2