QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#822006 | #9804. Guess the Polygon | wwww22 | WA | 1ms | 5836kb | C++20 | 1.9kb | 2024-12-19 20:28:01 | 2024-12-19 20:28:02 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define eb emplace_back
#define pi pair<ll,ll>
#define mk make_pair
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int N=5e5+10;
int n;
struct node
{
int x,y;
}a[N];
bool cmp(node a,node b)
{
if(a.x!=b.x)
{
return a.x<b.x;
}
else
{
return a.y<b.y;
}
}
db p,q;
db ask(int x)
{
cout<<"? "<<x<<" "<<1<<endl;
cin>>p>>q;
return p/q;
}
db an[N];
db ans;
ll aaa;
void solve(){
cin>>n;
ans=0;
an[1]=0;
an[n]=0;
fo(i,1,n)
{
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+n,cmp);
fo(i,2,n)
{
if(a[i].x==a[i-1].x)
{
goto SEC;
}
}
fo(i,2,n-1)
{
an[i]=ask(a[i].x);
}
fo(i,2,n)
{
ans+=(a[i].x-a[i-1].x)*(an[i]+an[i-1]);
// cout<<ans<<"\n";
}
// fo(i,1,n)
// {
// cout<<a[i].x<<" "<<a[i].y<<"\n";
// }
aaa=(ll)(ans+0.5);
if(aaa%2)
{
cout<<"! "<<aaa<<" "<<2<<endl;
}
else
{
cout<<"! "<<aaa/2<<" "<<1<<endl;
}
return;
SEC:
int f=0;
fo(i,2,n)
{
if(i==n)
{
if(a[i].x==a[i-1].x)
{
an[i]=an[i-1];
break;
}
if(f==0)
{
an[i]=an[i-1]/2;
break;
}
}
if(i>2&&(a[i].x==a[i-1].x))
{
an[i]=an[i-1];
if(i==n-1)
{
f=1;
}
continue;
}
else
{
int tmp=a[i].x+a[i-1].x;
if(tmp%2)
{
cout<<"? "<<tmp<<" "<<2<<endl;
cin>>p>>q;
an[i]=p/q;
}
else
{
an[i]=ask(tmp/2);
}
}
}
fo(i,2,n)
{
ans+=(a[i].x-a[i-1].x)*(an[i])*2;
// cout<<an[i]<<" "<<ans<<"\n";
}
aaa=(ll)(ans+0.5);
if(aaa%2)
{
cout<<"! "<<aaa<<" "<<2<<endl;
}
else
{
cout<<"! "<<aaa/2<<" "<<1<<endl;
}
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5712kb
input:
2 4 3 0 1 3 1 1 0 0 1 1 1 1 3 0 0 999 1000 1000 999 1999 1000
output:
? 1 2 ? 2 1 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
9 4 1 1 1 3 3 0 0 0 3 2 1 2 4 0 0 1 3 1 1 3 0 1 2 3 2 4 0 0 3 0 1 2 1 1 1 2 1 2 4 0 0 3 0 1 2 1 1 1 1 1 2 4 0 0 3 0 1 1 1 2 1 2 1 1 3 1000 0 0 0 0 1000 1000 1 4 0 0 1000 0 1000 1000 0 1000 1000 1 1000 1 5 0 1 1000 1000 1000 0 0 1000 1 0 999 1 1999 2 1000 1 9 4 1000 3 1 2 1000 3 1000 1 1 2 1 0 0 1 10...
output:
? 1 2 ? 2 1 ! 5 2 ? 1 2 ? 2 1 ! 7 2 ? 1 2 ? 2 1 ! 3 2 ? 1 2 ? 2 1 ! 2 1 ? 1 2 ? 2 1 ! 5 2 ? 0 1 ! 500000 1 ? 0 1 ? 500 1 ! 1000000 1 ? 0 1 ? 1 2 ? 1001 2 ! 1999999 2 ? 1 2 ? 3 2 ? 5 2 ? 7 2 ! 4003 2
result:
ok correct! (9 test cases)
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5836kb
input:
78 8 951 614 927 614 957 614 957 604 937 614 942 619 951 610 927 604 10 1 10 1 25 2 21 2 10 1 7 562 260 602 250 582 255 587 260 602 260 562 250 577 260 10 1 10 1 15 2 15 2 10 1 3 454 98 494 68 455 68 117 4 3 526 589 566 559 527 559 117 4 3 854 496 854 466 894 466 30 1 3 797 264 827 254 857 264 10 1 ...
output:
? 927 1 ? 932 1 ? 1879 2 ? 1893 2 ? 954 1 ! 317 1 ? 562 1 ? 1139 2 ? 1159 2 ? 1169 2 ? 1189 2 ! 375 1 ? 455 1 ! 585 1 ? 527 1 ! 585 1 ? 854 1 ! 600 1 ? 827 1 ! 300 1 ? 719 1 ! 600 1 ? 162 1 ! 400 1 ? 742 1 ? 1489 2 ? 1499 2 ? 772 1 ! 275 1 ? 932 1 ? 1869 2 ? 1879 2 ? 1889 2 ? 1899 2 ? 1909 2 ? 1919 ...
result:
wrong answer the answer is incorrect, expect: 525/2, find: 250/1 (test case 44)