QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#434874 | #8786. The Whole World | 致远星 (Penghao Zhai, Qiwen Xu, Xubei Zhong)# | ML | 1ms | 3956kb | C++14 | 7.9kb | 2024-06-08 17:45:55 | 2024-06-08 17:45:57 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double pi = acos(-1);
template<typename T> inline void chmax(T &nina, T momoka){ (nina<momoka) ? (nina=momoka) : 0; }
template<typename T> inline void chmin(T &nina, T momoka){ (momoka<nina) ? (nina=momoka) : 0; }
mt19937 rng(486);
inline int myrand(int l, int r){ return (int)(rng() % (r-l+1)) + l; }
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 binom[44][44];
int n, x[33], y[33];
vector<Int> coef[33];
void solve(){
cin >> n;
rep(i, n) cin >> x[i] >> y[i];
for(int K = 0; K <= 33; ++K){
for(int i = 0; i <= K; ++i){
coef[i].clear();
rep(j, n)
coef[i].push_back(binom[x[j]][i]);
}
vi p(n, -1);
for(int i = 0; i <= K; ++i){
rep(j, n) if(!coef[i][j].isZero()){
if(p[j] < 0){ p[j] = i; break; }
else {
while(!coef[i][j].isZero()){
Int cur = (coef[i][j] / coef[p[j]][j]).first;
rep(k, n) coef[i][k] = coef[i][k] - cur * coef[p[j]][k];
swap(coef[i], coef[p[j]]);
}
}
}
}
vector<Int> targ(n);
rep(i, n) targ[i] = y[i];
bool ok = 1;
rep(i, n) if(!targ[i].isZero()){
if(p[i] < 0){ ok = 0; break; }
Int cur = (targ[i] / coef[p[i]][i]).first;
rep(k, n) targ[k] = targ[k] - cur * coef[p[i]][k];
if(!targ[i].isZero()){ ok = 0; break; }
}
if(ok){
cout << K << "\n";
break;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
rep(i, 33) binom[0][i] = 0, binom[i][0] = 1;
for(int i = 1; i <= 32; ++i) for(int j = 1; j <= 32; ++j) binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3956kb
input:
2 2 1 0 4 1 3 1 1 4 4 6 6
output:
3 1
result:
ok 2 number(s): "3 1"
Test #2:
score: -100
Memory Limit Exceeded
input:
2 2 1 0 4 1 3 1 0 3 0 5 4