QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798084#9804. Guess the PolygonsnowysecretWA 6ms9844kbC++143.8kb2024-12-04 02:11:252024-12-04 02:11:26

Judging History

This is the latest submission verdict.

  • [2024-12-04 02:11:26]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 9844kb
  • [2024-12-04 02:11:25]
  • 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 / gcdd(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};
}
Fraction ask(Fraction give) {
  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 len = {0, 1};
  Fraction offset = {-1, 1000};
  Fraction ans = {0, 1};
  for(int i=2; i<=n-1; i++) {
    if(p[i].first == p[i-1].first && i > 2) continue;
    if(p[1].first == p[2].first && i == 2) {
      len = ask({p[1].first, 1});
    }
    else if(p[i].first != p[i+1].first) { // singleton
      Fraction newlen = ask({p[i].first, 1});
      ans = ans + (len + newlen) * frac(p[i].first - p[i-1].first, 2);
      len = newlen;
    }
    else {
      Fraction test = {p[i].first, 1};
      test = test + offset;
      Fraction q1 = ask(test);
      Fraction numer, denom;
      numer = q1 + frac(-len.p, len.q);
      //cout << "(" << q1.p << "/" << q1.q << " - " << p[i-1].first<<") / ";
      denom = frac(p[i].first - p[i-1].first, 1) + offset;
      //cout << "(" << p[i].first << " - " << p[i-1].first << " - 1/1000)\n";
      swap(denom.p, denom.q);
      Fraction factor = numer * denom;
      q1 = factor * frac(p[i].first - p[i-1].first, 1);
      //cout << "factor = " << factor.p << " / " << factor.q << endl;
      ans = ans + (len + q1) * frac(p[i].first - p[i-1].first, 2);
      Fraction newlen = ask({p[i].first, 1});
      len = newlen;
    }
    //cout << "Cumulative area: " << ans.p << " / " << ans.q << endl;
  }
  if(p[n-1].first != p[n].first) {
    ans = ans + len * frac(p[n].first - p[n-1].first, 2);
  }
  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
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9844kb

input:

2
4
3 0
1 3
1 1
0 0
999 500
2 1
3
0 0
999 1000
1000 999
1999 1000

output:

? 999 1000
? 1 1
! 3 1
? 999 1
! 1999 2

result:

ok correct! (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 9840kb

input:

9
4
1 1
1 3
3 0
0 0
2997 1000
3 1

output:

? 999 1000
? 1 1
! 9 2

result:

wrong answer the answer is incorrect, expect: 5/2, find: 9/2 (test case 1)