QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795914#9804. Guess the Polygonucup-team1134#WA 1ms3740kbC++233.2kb2024-12-01 04:10:302024-12-01 04:10:31

Judging History

This is the latest submission verdict.

  • [2024-12-01 04:10:31]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3740kb
  • [2024-12-01 04:10:30]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

//有理数

ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}

struct Rational{
    ll x,y;
    
    Rational(ll x=0,ll y=1):x(x),y(y){}
    
    Rational operator + (Rational p){
        ll z=y/gcd(y,p.y)*p.y;
        ll nx=z/y*x+z/p.y*p.x,ny=z;
        ll g=gcd(abs(nx),ny);
        return Rational(nx/g,ny/g);
    }
    Rational operator - (Rational p){
        ll z=y/gcd(y,p.y)*p.y;
        ll nx=z/y*x-z/p.y*p.x,ny=z;
        ll g=gcd(abs(nx),ny);
        return Rational(nx/g,ny/g);
    }
    Rational operator * (Rational p){
        ll nx=x*p.x,ny=y*p.y;
        if(ny<0){
            nx*=(-1);
            ny*=(-1);
        }
        ll g=gcd(abs(nx),abs(ny));
        return Rational(nx/g,ny/g);
    }
    Rational operator / (Rational p){
        ll nx=x*p.y,ny=y*p.x;
        if(ny<0){
            nx*=(-1);
            ny*=(-1);
        }
        ll g=gcd(abs(nx),abs(ny));
        return Rational(nx/g,ny/g);
    }
    
    bool operator < (const Rational &p)const{
        return x*p.y<y*p.x;
    }
    
    bool operator == (const Rational &p)const{
        return x*p.y==y*p.x;
    }
};


int main(){
    
    int Q;cin>>Q;
    while(Q--){
        ll N;cin>>N;
        vll S;
        vl use;
        for(int i=0;i<N;i++){
            ll a,b;cin>>a>>b;
            use.pb(a);
            S.pb(mp(a,b));
        }
        sort(all(S));
        mkunique(use);
        int l=0;
        vector<Rational> X;
        for(int i=0;i<si(use);i++){
            int r=l;
            while(r<N&&S[r].fi==use[i]) r++;
            if(i==0||i==si(use)-1){
                if(r-l>1){
                    cout<<"? "<<use[i]<<" "<<1<<endl;
                    ll a,b;cin>>a>>b;
                    X.pb(Rational{a,b});
                }else{
                    X.pb(Rational{0,1});
                }
            }else{
                cout<<"? "<<use[i]<<" "<<1<<endl;
                ll a,b;cin>>a>>b;
                X.pb(Rational{a,b});
            }
            
            l=r;
        }
        
        Rational ans={0,1};
        
        for(int i=0;i+1<si(use);i++){
            Rational su=X[i]+X[i+1];
            su=su*(use[i+1]-use[i]);
            ans=ans+su;
        }
        
        ans=ans*Rational{1,2};
        
        cout<<"! "<<ans.x<<" "<<ans.y<<endl;
    }
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3524kb

input:

9
4
1 1
1 3
3 0
0 0
3 1

output:

? 1 1
! 9 2

result:

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