QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812146#9804. Guess the Polygon275307894a#ML 0ms0kbC++1411.2kb2024-12-13 11:55:312024-12-13 11:55:31

Judging History

This is the latest submission verdict.

  • [2024-12-13 11:55:31]
  • Judged
  • Verdict: ML
  • Time: 0ms
  • Memory: 0kb
  • [2024-12-13 11:55:31]
  • Submitted

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';
}

Details

Tip: Click on the bar to expand more detailed information

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

result: