QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#822921#9804. Guess the Polygonucup-team2179#ML 0ms0kbC++238.6kb2024-12-20 17:28:362024-12-20 17:28:36

Judging History

This is the latest submission verdict.

  • [2024-12-20 17:28:36]
  • Judged
  • Verdict: ML
  • Time: 0ms
  • Memory: 0kb
  • [2024-12-20 17:28:36]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;

class Int {
public:
	using ll = long long;
	Int() {};
	Int(const string& s);
	Int(ll a) :Int(to_string(a)) {}
	Int(const Int& bInt) :nums(bInt.nums), isPositive(bInt.isPositive), length(bInt.length) {}
	Int(Int&& bInt) noexcept :nums(move(bInt.nums)), isPositive(bInt.isPositive), length(bInt.length) {}
	Int(const vector<int>& vec, bool sign = true) :nums(vec), isPositive(sign) { cutLeadZero(); }
	friend istream& operator >>(istream& is, Int& bInt) {
		string s;
		is >> s;
		bInt = move(Int(s));
		return is;
	}
	friend ostream& operator <<(ostream& os, const Int& bInt);
	operator string() const;
	const Int& operator +() const { return *this; }
	Int operator -() const {
		Int tmp(*this);
		if (!tmp.isZero())
			tmp.isPositive = !isPositive;
		return tmp;
	}
	bool operator <(const Int& bInt) const;
	bool operator <=(const Int& bInt) const;
	bool operator ==(const Int& bInt) const;
	Int operator +(const Int& bInt) const;
	Int operator -(const Int& bInt) const;
	Int operator *(const Int& bInt) const;
	// 除法会返回 商和余数
	pair<Int, Int> operator /(const Int& bInt) const;
	int operator[](int idx) const { return nums[idx]; }
	Int& operator =(const Int& bInt) {
		if (bInt == *this)
			return *this;
		nums = bInt.nums;
		isPositive = bInt.isPositive;
		length = bInt.length;
		return *this;
	}
	Int& operator =(Int&& bInt)noexcept {
		nums = move(bInt.nums);
		isPositive = bInt.isPositive;
		length = bInt.length;
		return *this;
	}
	size_t size() const { return nums.size(); }
	void cutLeadZero();
	bool isZero() const;
	Int absValue() const {
		return move(Int(nums));
	}
	static Int e(size_t n) {
		if (n <= 0)
			return move(Int(vector<int>(1, 1)));
		int m = n / digit;
		n -= m * digit;
		vector<int> ans(m);
		string s = "1";
		s += move(string(n, '0'));
		ans.push_back(stoi(s));
		return move(Int(ans));
	}
private:
	// 低位到高位
	vector<int> nums;
	bool isPositive = 1;
	int length = 0;
	static int digit;
	static int mod;
};
int Int::digit = 8;
int Int::mod = 100000000;
Int::Int(const string& s) {
	int n = s.size(), minIdx = 0;
	if(s[0]=='-')
		isPositive = false, minIdx = 1;
	else if(s[0]=='+')
		isPositive = true, minIdx = 1;
	for (int i = n - 1; i >= minIdx; i -= digit) {
		int beg = max(minIdx, i - digit + 1);
		nums.push_back(stoi(s.substr(beg, i - beg + 1)));
	}
	cutLeadZero();
}
ostream& operator <<(ostream& os, const Int& bInt) {
	os << (string)bInt;
	return os;
}
Int::operator string() const {
	string ans;
	if (!isPositive)
		ans += "-";
	int n = nums.size();
	for (int i = n - 1; i >= 0; i--) {
		string s = to_string(nums[i]);
		if (i != n - 1)
			ans += string(digit - s.size(), '0');
		ans += s;
	}
	return ans;
}
bool Int::operator<(const Int& bInt) const {
	if (isPositive && !bInt.isPositive)
		return false;
	if (!isPositive && bInt.isPositive)
		return true;
	bool flag = true;
	if (!isPositive)
		flag = false;
	if (length < bInt.length)
		return flag;
	else if (length > bInt.length)
		return !flag;
	int n = size();
	for (int i = n - 1; i >= 0; i--) {
		if (nums[i] < bInt[i])
			return flag;
		else if (nums[i] > bInt[i])
			return !flag;
	}
	return false;
}
bool Int::operator<=(const Int& bInt) const {
	if (isPositive && !bInt.isPositive)
		return false;
	if (!isPositive && bInt.isPositive)
		return true;
	bool flag = true;
	if (!isPositive)
		flag = false; // 都为负数
	if (length < bInt.length)
		return flag;
	else if (length > bInt.length)
		return !flag;
	int n = size();
	for (int i = n - 1; i >= 0; i--) {
		if (nums[i] < bInt[i])
			return flag;
		else if (nums[i] > bInt[i])
			return !flag;
	}
	return true;
}
bool Int::operator==(const Int& bInt) const {
	if (length != bInt.length)
		return false;
	int n = size();
	for (int i = 0; i < n; i++)
		if (nums[i] != bInt[i])
			return false;
	return true;
}
Int Int::operator+(const Int& bInt) const {
	if (!bInt.isPositive)
		return *this - (-bInt);
	if (!isPositive)
		return bInt - (-*this);
	vector<int> ans;
	int n = size(), m = bInt.size(), sum = 0, i = 0, j = 0;
	while (i < n || j < m || sum)
	{
		if (i < n)
			sum += nums[i++];
		if (j < m)
			sum += bInt[j++];
		ans.push_back(sum % mod);
		sum /= mod;
	}
	return move(Int(ans, isPositive));
}
Int Int::operator-(const Int& bInt) const
{
	if (!bInt.isPositive)
		return *this + (-bInt);
	if (!isPositive)
		return -((-*this) + bInt);
	if (*this < bInt)
		return -(bInt - *this);
	vector<int> ans;
	int i = 0, j = 0, n = size(), m = bInt.size(), sum = 0;
	while (i < n || j < m || sum) {
		if (i < n)
			sum += nums[i++];
		if (j < m)
			sum -= bInt[j++];
		int flag = 0;
		if (sum < 0) {
			flag = -1;
			sum += mod;
		}
		ans.push_back(sum);
		sum = flag;
	}
	return move(Int(ans));
}
Int Int::operator*(const Int& bInt) const {
	int n = size(), m = bInt.size();
	vector<int> ans(n + m);
	using ll = long long;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ll tmp = ans[i + j] + nums[i] * 1ll * bInt[j];
			ans[i + j] = tmp % mod;
			ans[i + j + 1] += tmp / mod;
		}
	}
	return move(Int(ans, isPositive == bInt.isPositive));
}
pair<Int, Int> Int::operator/(const Int& bInt) const {
	Int a = absValue();
	Int b = bInt.absValue();
	if (b.isZero())
		return pair<Int, Int>(*this, move(b));
	if (a < b)
		return pair<Int, Int>(move(Int(0)), *this);
	int len = a.length - b.length + 1;
	string ans;
	if (isPositive != bInt.isPositive)
		ans = "-";
	for (int i = 0; i < len; i++) {
		Int tmp = e(len - i - 1) * b;
		int times = 0;
		while (tmp <= a) {
			a = a - tmp;
			++times;
		}
		ans += times + '0';
	}
	a.isPositive = isPositive;
	return pair<Int, Int>(move(Int(ans)), move(a));
}
void Int::cutLeadZero() {
	while(nums.size() > 1 && nums.back() == 0)
		nums.pop_back();
	if(nums.empty()) length = 0;
	else length = (nums.size() - 1) * digit + to_string(nums.back()).size();
}
bool Int::isZero() const {
	return nums.size() == 1 && nums.back() == 0;
}

Int biggcd(Int a,Int b){
    if(a<Int(0))a=-a;
    if(b<Int(0))b=-b;
    if(b==Int(0ll))return a;
    if(a<b)swap(a,b);
    return biggcd(b,(a/b).second);
}

struct num{
    Int a,b;
    num(Int x,Int y){
        Int d=biggcd(x,y);
        a=(x/d).first;
        b=(y/d).first;
    }
    num(){a=0,b=1;}
    num(Int x){
        a=x;
        b=1;
    }
    num operator+(num y){
        return num(a*y.b+y.a*b,b*y.b);
    }
    num operator*(num y){
        return num(a*y.a,b*y.b);
    }
    num operator/(num y){
        return num(a*y.b,b*y.a);
    }
    num operator-(num y){
        return num(a*y.b-y.a*b,b*y.b);
    }
};
struct Point 
{
    num x,y;
    Point(){}
    Point(num a,num b){
        x=a,y=b;
    }
};
num getval(Point a1,Point a2,num x){
    auto [x1,y1]=a1;
    auto [x2,y2]=a2;
    return y1+(y2-y1)/(x2-x1)*(x-x1);
}
num query(num u){
    cout<<"? "<<u.a<<" "<<u.b<<endl;
    int x,y;
    cin>>x>>y;
    return num(x,y);
}

num diff=num(1,5);

void solve() {
    int n;
    cin>>n;
    vector<int>vx;
    map<int,int>mp;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        mp[x]++;
    }
    for(auto [x,cnt]:mp){
        vx.pb(x);
    }
    n=vx.size();
    Point val[n][2];
    num ans(0);
    if(mp[vx[0]]>1){
        num now=query(num(vx[0])+diff);
        val[0][1]=Point(num(vx[0])+diff,now);
    }
    else {
        num now=num(0);
        val[0][1]=Point(num(vx[0]),now);
    }

    if(mp[vx[n-1]]>1){
        num now=query(num(vx[n-1])-diff);
        val[n-1][0]=Point(num(vx[n-1])-diff,now);
    }
    else {
        num now=num(0);
        val[n-1][0]=Point(num(vx[n-1]),now);
    }
    for(int i=1;i<n-1;i++){
        if(mp[vx[i]]==1){
            num now=query(num(vx[i]));
            val[i][0]=Point(num(vx[i]),now);
            val[i][1]=Point(num(vx[i]),now);
        }
        else {
            num now=query(num(vx[i])-diff);
            val[i][0]=Point(num(vx[i])-diff,now);
            now=query(num(vx[i])+diff);
            val[i][1]=Point(num(vx[i])+diff,now);
        }
    }

    for(int i=0;i<n-1;i++){
        num high=num(vx[i+1]-vx[i]);
        num len1=getval(val[i][1],val[i+1][0],num(vx[i]));
        num len2=getval(val[i][1],val[i+1][0],num(vx[i+1]));
        ans=ans+high*(len1+len2)/num(2);
    }
    cout<<"! "<<ans.a<<" "<<ans.b<<endl;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

2
4
3 0
1 3
1 1
0 0
8 5
9 5
3
0 0
999 1000
1000 999
1999 1000

output:

? 4 5
? 6 5
! 3 1
? 999 1

result: