QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #812146 | #9804. Guess the Polygon | 275307894a# | ML | 0ms | 0kb | C++14 | 11.2kb | 2024-12-13 11:55:31 | 2024-12-13 11:55:31 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e3+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
namespace cmyInteger
{
typedef long long ll;
typedef unsigned long long ull;
class __int256
{
private:
const static int N=2333,base=1e8;
int a[N],len,neg;
void write(int _a)const{if(_a>9)write(_a/10);putchar((_a%10)|48);}
int getlen(int _a)const{int ans=0;while(_a)_a/=10,++ans;return ans;}
public:
__int256(){len=1,neg=0,memset(a,0,sizeof(a));}
__int256(char *s)
{
memset(a,0,sizeof(a));
if(s[0]=='-')
{
int slen=strlen(s)-1;
len=1,neg=1;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i+1]^48);
k*=10;
}
}
else
{
int slen=strlen(s);
len=1,neg=0;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i]^48);
k*=10;
}
}
}
__int256(std::string s)
{
memset(a,0,sizeof(a));
if(s[0]=='-')
{
int slen=s.size()-1;
len=1,neg=1;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i+1]^48);
k*=10;
}
}
else
{
int slen=s.size();
len=1,neg=0;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i]^48);
k*=10;
}
}
}
__int256(const char *s)
{
memset(a,0,sizeof(a));
if(s[0]=='-')
{
int slen=strlen(s)-1;
len=1,neg=1;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i+1]^48);
k*=10;
}
}
else
{
int slen=strlen(s);
len=1,neg=0;
int k=1;
for(int i=1;i<=slen;++i)
{
if(k==base)++len,k=1;
a[len]+=k*(s[slen-i]^48);
k*=10;
}
}
}
template<typename _Tp>__int256(_Tp x)
{
memset(a,0,sizeof(a));
if(x<0)x=-x,neg=1;
len=0;
int tmp;
while((tmp=x/base))
{
a[++len]=x%base;
x=tmp;
}
a[++len]=x;
}
void get()
{
std::string s=std::string();
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-'&&!s.size())s+='-';
ch=getchar();
}
while(ch>='0'&&ch<='9')s+=ch,ch=getchar();
*this=__int256(s);
}
void print()const
{
int baselen=getlen(base)-1;
if(neg)putchar('-');
write(a[len]);
for(int i=len-1,tmp;i;--i)
{
tmp=baselen-getlen(a[i]);
while(tmp--)putchar('0');
write(a[i]);
}
}
friend std::istream& operator>>(std::istream& input,__int256& x)
{
x.get();
return input;
}
friend std::ostream& operator<<(std::ostream& output,const __int256& x)
{
x.print();
return output;
}
bool operator==(const __int256& x)const
{
if(len!=x.len||neg!=x.neg)return false;
for(int i=1;i<=len;++i)if(a[i]!=x.a[i])return false;
return true;
}
bool operator!=(const __int256& x)const{return !(*this==x);}
bool operator>(const __int256& x)const
{
if(neg!=x.neg)return x.neg;
if(len!=x.len)return len>x.len;
for(int i=len;i;--i)if(a[i]!=x.a[i])return a[i]>x.a[i];
return false;
}
bool operator<(const __int256& x)const
{
if(neg!=x.neg)return neg;
if(len!=x.len)return len<x.len;
for(int i=len;i;--i)if(a[i]!=x.a[i])return a[i]<x.a[i];
return false;
}
bool operator>=(const __int256& x)const{return !(*this<x);}
bool operator<=(const __int256& x)const{return !(*this>x);}
__int256 operator-()const{__int256 x(*this);x.neg^=1;return x;}
__int256 operator+(const __int256& x)const
{
if((!neg)&&x.neg)return *this-(-x);
if(neg&&(!x.neg))return x-(-*this);
__int256 ans=__int256();
ans.len=std::max(len,x.len);
for(int i=1;i<=ans.len;++i)
{
ans.a[i]+=a[i]+x.a[i];
if(ans.a[i]>=base)ans.a[i]-=base,++ans.a[i+1];
}
if(ans.a[ans.len+1])++ans.len;
if(neg&&x.neg)ans.neg=1;
return ans;
}
__int256 operator+=(const __int256& x){return *this=*this+x;}
__int256 operator-(const __int256& x)const
{
if((!neg)&&x.neg)return *this+(-x);
if(neg&&x.neg)return (-x)-(-*this);
if(neg&&(!x.neg))return -((-*this)+x);
__int256 ans=__int256();
if(*this==x)return ans;
if(x>*this)
{
ans=(x-*this);
ans.neg=1;
return ans;
}
ans.len=std::max(len,x.len);
for(int i=1;i<=ans.len;++i)
{
ans.a[i]+=a[i]-x.a[i];
if(ans.a[i]<0)ans.a[i]+=base,--ans.a[i+1];
}
while(ans.len&&!ans.a[ans.len])--ans.len;
return ans;
}
__int256 operator-=(const __int256& x){return *this=*this-x;}
__int256 operator*(const __int256& x)const
{
__int256 ans=__int256();
if(*this==ans||x==ans)return ans;
if(neg!=x.neg)ans.neg=1;
ans.len=std::max(len,x.len);
ull tmp;
for(int i=1;i<=len;++i)
for(int j=1;j<=x.len;++j)
{
tmp=1ull*a[i]*x.a[j]+ans.a[i+j-1];
if(tmp>=base)
{
ans.a[i+j]+=tmp/base;
ans.a[i+j-1]=tmp%base;
}
else ans.a[i+j-1]=tmp;
}
while(ans.a[ans.len]>0)++ans.len;
--ans.len;
return ans;
}
__int256 operator*=(const __int256& x){return *this=*this*x;}
__int256 operator/(const __int256& X)const
{
if(X==0)std::cerr<<"Error:divide 0\n",exit(-1);
__int256 ans(*this),x(X),tmp(1),lt=__int256();
if(neg!=x.neg)ans.neg=1;
while(ans>=x) x*=2,tmp*=2;
while(tmp.len>1||tmp.a[1])
{
if(ans>=x) ans-=x,lt+=tmp;
x/=2,tmp/=2;
}
ans=lt;
while(ans.len&&!ans.a[ans.len])--ans.len;
if(!ans.len)return __int256();
return ans;
}
__int256 operator/=(const __int256& X)
{
if(X==0)std::cerr<<"Error:divide 0\n",exit(-1);
__int256 x(X),tmp(1),lt=__int256();
if(neg!=x.neg)neg=1;
else neg=0;
while(*this>=x) x*=2,tmp*=2;
while(tmp.len>1||tmp.a[1])
{
if(*this>=x) *this-=x,lt+=tmp;
x/=2,tmp/=2;
}
*this=lt;
while(len&&!a[len])--len;
if(!len)return *this=__int256();
return *this;
}
__int256 operator%(const __int256& X)const
{
if(X==0)std::cerr<<"Error:mod 0\n",exit(-1);
__int256 ans(*this),x(X),tmp(1),lt=__int256();
if(neg!=x.neg)ans.neg=1;
while(ans>=x) x*=2,tmp*=2;
while(tmp.len>1||tmp.a[1])
{
if(ans>=x) ans-=x,lt+=tmp;
x/=2,tmp/=2;
}
return ans;
}
__int256 operator%=(const __int256& X)
{
if(X==0)std::cerr<<"Error:mod 0\n",exit(-1);
__int256 x(X),tmp(1),lt=__int256();
if(neg!=x.neg)neg=1;
else neg=0;
while(*this>=x) x*=2,tmp*=2;
while(tmp.len>1||tmp.a[1])
{
if(*this>=x) *this-=x,lt+=tmp;
x/=2,tmp/=2;
}
return *this;
}
template<typename _Tp>operator _Tp()const{return _Tp(a[1]);}
template<typename _Tp>__int256 operator+(const _Tp& x)const{return *this+__int256(x);}
template<typename _Tp>__int256 operator+=(const _Tp& x){return *this=*this+x;}
template<typename _Tp>__int256 operator-(const _Tp& x)const{return *this-__int256(x);}
template<typename _Tp>__int256 operator-=(const _Tp& x){return *this=*this-x;}
template<typename _Tp>__int256 operator*(const _Tp& x)const
{
__int256 ans=__int256();
if(*this==ans||x==0)return ans;
if(neg!=(x<0))ans.neg=1;
ans.len=len;
ull tmp;
for(int i=1;i<=len;++i)
{
tmp=1ull*a[i]*x+ans.a[i];
if(tmp>=base)
{
ans.a[i]=tmp%base;
ans.a[i+1]+=tmp/base;
}
else ans.a[i]=tmp;
}
while(ans.a[ans.len]>0)++ans.len;
--ans.len;
return ans;
}
template<typename _Tp>__int256 operator*=(const _Tp& x){return *this=*this*x;}
template<typename _Tp>__int256 operator/(const _Tp& x)const
{
if(x==0)std::cerr<<"Error:divide 0\n",exit(-1);
__int256 ans=__int256();
if(len==1&&x>a[1])return ans;
ull res=0;
if(neg!=(x<0))ans.neg=1;
for(int i=len;i;--i)
{
res=res*base+a[i];
ans.a[i]=res/x;
res%=x;
}
while(ans.a[ans.len]>0)++ans.len;
--ans.len;
return ans;
}
template<typename _Tp>__int256 operator/=(const _Tp& x){return *this=*this/x;}
template<typename _Tp>__int256 operator%(const _Tp& x)const
{
if(x==0)std::cerr<<"Error:mod 0\n",exit(-1);
if(len==1&&x>a[1])return *this;
ull res=0;
for(int i=len;i;--i)
{
res=res*base+a[i];
res%=x;
}
return res;
}
template<typename _Tp>__int256 operator%=(const _Tp& x){return *this=*this%x;}
};
template<typename _Tp>const __int256 operator+(const _Tp& x,const __int256& y){return __int256(x)+y;}
template<typename _Tp>const __int256 operator-(const _Tp& x,const __int256& y){return __int256(x)-y;}
template<typename _Tp>const __int256 operator*(const _Tp& x,const __int256& y){return __int256(x)*y;}
template<typename _Tp>const __int256 operator/(const _Tp& x,const __int256& y){return __int256(x)/y;}
template<typename _Tp>const __int256 operator%(const _Tp& x,const __int256& y){return __int256(x)%y;}
};
using namespace cmyInteger;
int n,A[N],B[N],m;
using LL=__int256;
using frac=pair<LL,LL>;
frac operator +(const frac &A,const frac &B){
LL g=__gcd(A.se,B.se);
return frac(B.se/g*A.fi+A.se/g*B.fi,A.se/g*B.se);
}
frac operator -(const frac &A,const frac &B){
return A+frac(-B.fi,B.se);
}
frac operator *(const frac &A,const frac &B){
return frac(A.fi*B.fi,A.se*B.se);
}
frac operator /(const frac &A,const frac &B){
return A*frac(B.se,B.fi);
}
frac query(ll x,ll y){
cout<<"? "<<x<<' '<<y<<endl;
cin>>x>>y;
return frac(x,y);
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+48);
}
void Solve(){
cin>>n;m=n;
Me(B,0);
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
A[i]=x;B[x]++;
}
sort(A+1,A+n+1);m=unique(A+1,A+n+1)-A-1;
frac La=frac(0,1),ans=frac(0,1);
for(int i=1;i<m;i++){
int px=A[i]*3+1,py=A[i+1]*3-1;
frac w1,w2;
if(B[A[i]]>=2) w1=query(px,3);
else w1=La,px--;
if(i==m-1&&B[A[m]]==1) w2=frac(0,1),py++;
else w2=query(py,3);
frac d=(w2-w1)/frac(py-px,1);
if(px==A[i]*3+1) px--,w1=w1-d;
if(py==A[i+1]*3-1) py++,w2=w2+d;
ans=ans+(w1+w2)*frac(A[i+1]-A[i],2);
La=w2;
}
if(ans.fi<0) ans.fi*=-1,ans.se*=-1;
LL g=__gcd(ans.fi,ans.se);
cout<<"! ";
print(ans.fi/g);
cout<<" ";
print(ans.se/g);
cout<<endl;
}
int main(){
// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int t=1;
scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
2 4 3 0 1 3 1 1 0 0 4 3 5 3 3 0 0 999 1000 1000 999 1497251 749250
output:
? 2 3 ? 4 3 ! 3 1 ? 2996 3