QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352605#5110. SplitstreamPorNPtree#WA 0ms4556kbC++1415.1kb2024-03-13 13:59:132024-03-13 13:59:13

Judging History

你现在查看的是最新测评结果

  • [2024-03-13 13:59:13]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：4556kb
查看
  • [2024-03-13 13:59:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
class BigIntNums
{
    friend ostream &operator<<(ostream &, const BigIntNums &);
    friend istream &operator>>(istream &, BigIntNums &);
    friend BigIntNums operator-(const BigIntNums &);
    friend BigIntNums operator+(const BigIntNums &, const BigIntNums &);
    friend BigIntNums operator+(const BigIntNums &, const int &);
    friend BigIntNums operator*(const BigIntNums &, const BigIntNums &);
    friend BigIntNums operator-(const BigIntNums &, const BigIntNums &);
    friend BigIntNums operator/(const BigIntNums &, const BigIntNums &);
    friend BigIntNums operator%(const BigIntNums &, const BigIntNums &);
    friend bool operator<(const BigIntNums &, const BigIntNums &);
    friend bool operator>(const BigIntNums &, const BigIntNums &);
    friend bool operator<=(const BigIntNums &, const BigIntNums &);
    friend bool operator>=(const BigIntNums &, const BigIntNums &);
    friend bool operator==(const BigIntNums &, const BigIntNums &);
    friend bool operator!=(const BigIntNums &, const BigIntNums &);
    operator int() = delete;
public:
    BigIntNums() = default;
    BigIntNums(const BigIntNums &);
    BigIntNums(const string &);
    BigIntNums(const int &);
    BigIntNums(const unsigned int &);
    BigIntNums(const long long &);
    BigIntNums(const unsigned long long &);

    operator bool();
    BigIntNums &operator++();
    BigIntNums &operator--();
    BigIntNums &operator=(const BigIntNums &);
    BigIntNums &operator+=(const BigIntNums &);
    BigIntNums &operator*=(const BigIntNums &);
    BigIntNums &operator-=(const BigIntNums &);
    BigIntNums &operator/=(const BigIntNums &);
    string getStr();
private:
    static constexpr size_t gap_ = 10000;
    static constexpr size_t base_ = 10;

    std::vector<int> numMem;
    bool npFlag = true;

    void combineStrToBigInt(const string &);
    template<typename T>void loadNums(T);
    void clear();
};
template<typename T>void BigIntNums::loadNums(T num)
{
    numMem.clear();
    while (num / gap_)
    {
        numMem.push_back(static_cast<int>(num%gap_));
        num /= gap_;
    }
    numMem.push_back(static_cast<int>(num));
}

ostream &operator<<(ostream &os, const BigIntNums &num)
{
    if (num.npFlag == false)
        os << '-';
    os << num.numMem[num.numMem.size() - 1] << " ";
    os << setfill('0') << right;
    int cut = static_cast<int>(log10(BigIntNums::gap_));
    for(int i = num.numMem.size() - 2;i >=0 ;i--)
        os << setw(cut) << num.numMem[i] << " ";
    os << setfill(' ') << left;
    return os;
}

istream &operator>>(istream &is, BigIntNums &num)
{
    num.clear();
    string str;
    is >> str;
    num.combineStrToBigInt(str);
    return is;
}

BigIntNums::BigIntNums(const BigIntNums &ob)
    :numMem(ob.numMem)
    , npFlag(ob.npFlag)
{ }

BigIntNums::BigIntNums(const int &num)
{
    loadNums(num);
    npFlag = num >= 0 ? true : false;
}

BigIntNums::BigIntNums(const unsigned int &num)
{
    loadNums(num);
    npFlag = true;
}

BigIntNums::BigIntNums(const long long &num)
{
    loadNums(num);
    npFlag = num >= 0 ? true : false;
}

BigIntNums::BigIntNums(const unsigned long long &num)
{
    loadNums(num);
    npFlag = true;
}

BigIntNums::BigIntNums(const string &str_org)
{
    combineStrToBigInt(str_org);
}

inline void BigIntNums::clear()
{
    numMem.clear();
    npFlag = true;
}

void BigIntNums::combineStrToBigInt(const string &str_org)
{
    int base_Count = static_cast<int>(log10(BigIntNums::gap_));

    string str = str_org;
    reverse(str.begin(), str.end());
    if (!isalnum(str.back()))
    {
        npFlag = str.back() == '+' ? 1 : 0;
        str.pop_back();
    }
    int cnt = str.size() - base_Count, i;
    for (i = 0; i < cnt; i += 4)
    {
        string cast = str.substr(i, base_Count);
        reverse(cast.begin(), cast.end());
        int tmp = atoi(cast.c_str());
        numMem.push_back(tmp);
    }
    string cast = str.substr(i, str.size());
    reverse(cast.begin(), cast.end());
    int tmp = atoi(cast.c_str());
    numMem.push_back(tmp);
}

string BigIntNums::getStr()
{
    string tmp;

    for (auto i = numMem.crbegin();i != numMem.crend();++i)
    {
        stringstream cast;
        cast << *i;
        tmp += cast.str();
    }
    return tmp;
}

BigIntNums::operator bool()
{
    return *this != BigIntNums(0);
}

bool operator==(const BigIntNums &A, const BigIntNums &B)
{
    if (A.npFlag != B.npFlag)
        return false;
    else if (A.numMem.size() != B.numMem.size())
        return false;
    else
    {
        for (int i = 0;i < A.numMem.size();i++)
            if (A.numMem[i] != B.numMem[i])
                return false;
    }
    return true;
}

bool operator!=(const BigIntNums &A, const BigIntNums &B)
{
    return !(A == B);
}

bool operator<(const BigIntNums &A, const BigIntNums &B)
{
    if (A.npFlag == true && B.npFlag == false)
        return false;
    else if (A.npFlag == false && B.npFlag == true)
        return true;
    else
    {
        auto ret = A.npFlag && B.npFlag;
        if (A.numMem.size() > B.numMem.size())
            return !ret;
        else if (A.numMem.size() < B.numMem.size())
            return ret;
        else if (A.numMem.size() == B.numMem.size())
        {
            for (int i = A.numMem.size() - 1;i >= 0;i--)
            {
                if (A.numMem[i] > B.numMem[i])
                    return !ret;
                else if (A.numMem[i] < B.numMem[i])
                    return ret;
            }
        }
        return false;//相等
    }
}

bool operator>(const BigIntNums &A, const BigIntNums &B)
{
    if (A.npFlag == false && B.npFlag == true)
        return false;
    else if (A.npFlag == true && B.npFlag == false)
        return true;
    else
    {
        auto ret = A.npFlag && B.npFlag;
        if (A.numMem.size() > B.numMem.size())
            return ret;
        else if (A.numMem.size() < B.numMem.size())
            return !ret;
        else if (A.numMem.size() == B.numMem.size())
        {
            for (int i = A.numMem.size() - 1;i >= 0;i--)
            {
                if (A.numMem[i] > B.numMem[i])
                    return ret;
                else if (A.numMem[i] < B.numMem[i])
                    return !ret;
            }
        }
        return false;//相等
    }
}

bool operator<=(const BigIntNums &A, const BigIntNums &B)
{
    return  A < B || A == B;
}

bool operator>=(const BigIntNums &A, const BigIntNums &B)
{
    return A > B || A == B;
}

BigIntNums abs(const BigIntNums &i)
{
    return i >= 0 ? i : -i;
}

BigIntNums operator-(const BigIntNums &num)
{
    BigIntNums newNum(num);
    newNum.npFlag = !num.npFlag;
    return newNum;
}

BigIntNums operator+(const BigIntNums &A, const BigIntNums &B)
{
    BigIntNums C;

    if (A.npFlag == true && B.npFlag == true)
        C.npFlag = true;
    else if (A.npFlag == false && B.npFlag == false)
        C.npFlag = false;
    else if (A.npFlag == true && B.npFlag == false)
        return A - (-B);
    else if (A.npFlag == false && B.npFlag == true)
        return B - (-A);

    std::vector<int> &CM = C.numMem;
    const std::vector<int> &AM = A.numMem, &BM = B.numMem;

    int up = 0, tmp;
    size_t cnt = std::min(A.numMem.size(), B.numMem.size()), i = 0;

    for (;i < cnt; i++)
    {
        tmp = AM[i] + BM[i] + up;
        CM.push_back(tmp % BigIntNums::gap_);
        up = tmp / BigIntNums::gap_;
    }
    //要注意可能会出现1+999999999999999999999999999的情况
    for (;i < AM.size(); i++)
    {
        tmp = AM[i] + up;
        CM.push_back((AM[i] + up) % BigIntNums::gap_);
        up = (AM[i] + up) / BigIntNums::gap_;
    }
    for (;i < BM.size(); i++)
    {
        tmp = BM[i] + up;
        CM.push_back((BM[i] + up) % BigIntNums::gap_);
        up = (BM[i] + up) / BigIntNums::gap_;
    }
    if(up)
        CM.push_back(up);
    return C;
}

BigIntNums operator+(const BigIntNums &A, const int &B)
{
    return A + BigIntNums(B);
}

BigIntNums operator-(const BigIntNums &A, const int &B)
{
    return A - BigIntNums(B);
}
BigIntNums operator*(const BigIntNums &A, const int &B)
{
    return A * BigIntNums(B);
}
BigIntNums operator/(const BigIntNums &A, const int &B)
{
    return A / BigIntNums(B);
}
BigIntNums operator%(const BigIntNums &A, const int &B)
{
    return A % BigIntNums(B);
}
BigIntNums operator-(const BigIntNums &A, const BigIntNums &B)
{
    BigIntNums C;
    C.npFlag = true;
    if (A.npFlag == true && B.npFlag == true && A < B)
    {
        C = B - A;
        C.npFlag = false;
        return C;
    }
    else if (A.npFlag == false && B.npFlag == false)
        return (-B) - (-A);
    else if (A.npFlag == true && B.npFlag == false)
        return A + (-B);
    else if (A.npFlag == false && B.npFlag == true)
    {
        C = (-A) + B;
        C.npFlag = false;
        return C;
    }

    std::vector<int> &CM = C.numMem;
    const std::vector<int> &AM = A.numMem, &BM = B.numMem;

    int down = 0,  tmp;
    size_t cnt = B.numMem.size(), i = 0;

    for (;i < cnt; i++)
    {
        if (AM[i] - BM[i] - down >= 0)
        {
            tmp = AM[i] - BM[i] - down;
            down = 0;
        }
        else
        {
            tmp = BigIntNums::gap_ + AM[i] - BM[i] - down;
            down = 1;
        }
        CM.push_back(tmp);
    }
    //注意1000000000000000-1的情况
    for (;i < A.numMem.size();i++)
    {
        if (AM[i] - down >= 0)
        {
            tmp = AM[i] - down;
            down = 0;
        }
        else
        {
            tmp = BigIntNums::gap_ + AM[i] - down;
            down = 1;
        }
        CM.push_back(tmp);
    }
    while(C.numMem.back() == 0 && CM.size() != 1)
        //如果只剩下0，那还是要保留0
        C.numMem.pop_back();
    return C;
}

BigIntNums operator*(const BigIntNums &A, const BigIntNums &B)
{
    BigIntNums C;
    C.npFlag = true;

    if (A.npFlag == false && B.npFlag == true
        || A.npFlag == true && B.npFlag == false)
        C.npFlag = false;

    if (abs(A) < abs(B))
        return B*A;

    if (A == 0 || B == 0)
        return BigIntNums(0);

    const std::vector<int> &AM = A.numMem, &BM = B.numMem;
    std::vector<int> &CM = C.numMem;

    int up = 0, tmp;

    for (int i = 0; i < AM.size();i++,up = 0)
    {
        for (int j = 0; j < BM.size();j++)
        {
            tmp = AM[i] * BM[j] + up;
            if (i + j < CM.size())
            {
                up = (tmp + CM[i + j]) / BigIntNums::gap_;
                CM[i + j] = (tmp + CM[i + j]) % BigIntNums::gap_;
            }
            else
            {
                up = tmp / BigIntNums::gap_;
                CM.push_back(tmp % BigIntNums::gap_);
            }
        }
        if (up)
            CM.push_back(up);
    }
    return C;
}

BigIntNums operator/(const BigIntNums &A, const BigIntNums &B)
{
    int base_Count = static_cast<int>(log10(BigIntNums::gap_));

    if (abs(A) < abs(B))
        return BigIntNums(0);
    BigIntNums C;
    C.npFlag = true;

    if (A.npFlag == false && B.npFlag == true
        || A.npFlag == true && B.npFlag == false)
        C.npFlag = false;

    int base_Map, tmp;
    std::vector<int> rCM;
    std::vector<int> &CM = C.numMem;
    const std::vector<int> &AM = A.numMem, &BM = B.numMem;
    BigIntNums dividend = 0, divisor;
    auto CM_Iter = CM.rbegin();

    for (int i = AM.size() - 1; i >= 0;)
    {
        do {
            dividend *= static_cast<int>(pow(BigIntNums::base_, base_Count));
            dividend += AM[i--];
        } while (dividend < B && i >= 0);

        tmp = 0;
        for (int j = base_Count - 1;j >= 0;j--)
        {
            for (int k = BigIntNums::base_ - 1;;k--)
            {
                base_Map = static_cast<int>(pow(BigIntNums::base_, j)) * k;
                auto tmp = abs(B);
                BigIntNums y = tmp * BigIntNums(base_Map);
                if (y <= dividend)
                    break;
            }
            dividend -= abs(B) * BigIntNums(base_Map);
            tmp += base_Map;
        }
        rCM.push_back(tmp);
    }
    for (auto i = rCM.crbegin();i != rCM.crend();++i)
        CM.push_back(*i);
    while (C.numMem.back() == 0 && CM.size() != 1)
        C.numMem.pop_back();

    return C;
}

BigIntNums operator%(const BigIntNums &A, const BigIntNums &B)
{
    auto ret = A / B;
    return A - ret*B;
}

BigIntNums &BigIntNums::operator++()
{
    *this = *this + BigIntNums(1);
    return *this;
}

BigIntNums &BigIntNums::operator--()
{
    *this = *this - BigIntNums(1);
    return *this;
}

BigIntNums &BigIntNums::operator=(const BigIntNums &ob)
{
    if (&ob != this)
    {
        this->numMem = ob.numMem;
        this->npFlag = ob.npFlag;
    }
    return *this;
}

BigIntNums &BigIntNums::operator+=(const BigIntNums &ob)
{
    *this = *this + ob;
    return *this;
}

BigIntNums &BigIntNums::operator-=(const BigIntNums &ob)
{
    *this = *this - ob;
    return *this;
}

BigIntNums &BigIntNums::operator*=(const BigIntNums &ob)
{
    *this = *this * ob;
    return *this;
}

BigIntNums &BigIntNums::operator/=(const BigIntNums &ob)
{
    *this = *this / ob;
    return *this;
}
const int N=2e4+10;
const long long inf=1e18;
int pre[N],nxt[N];
struct node
{
    int o,x,y,z;
}e[N];
int m,n,q;
BigIntNums len[N];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>m>>n>>q;
    len[1]=m;
    for(int i=1;i<=n;++i)
    {
        char s[10];
        int x,y,z;
        cin>>s>>x>>y>>z;
        e[i]=node{*s=='S',x,y,z};
        if(*s=='S')
        {
            pre[y]=pre[z]=nxt[x]=i;
            len[y]=(len[x]+1)/2,
            len[z]=len[x]/2;
        }
        else
        {
            pre[z]=nxt[x]=nxt[y]=i;
            len[z]=len[x]+len[y];
        }
    }
    while(q--)
    {
        long long x;
        BigIntNums k;
        cin>>x>>k;
        // cerr<<endl;
        if(len[x]<k){cout<<"none\n";continue;}
        while(x!=1)
        {
            int i=pre[x];
            // cerr<<x<<": "<<k<<" "<<pre[x]<<" : "<<e[i].o<<","<<e[i].x<<","<<e[i].y<<","<<e[i].z<<endl;;
            if(e[i].o==1)//Split
            {
                k=k*2-(e[i].y==x);
                x=e[i].x;
            }
            else//Merge
            {
                BigIntNums mn=min(len[e[i].x],len[e[i].y]);
                if(k>mn*2)
                {
                    k-=mn;
                    int mx=len[e[i].x]>len[e[i].y]?e[i].x:e[i].y;
                    x=mx;
                }
                else
                {
                    if(k%2)//from x
                    {
                        k=(k+1)/2;
                        x=e[i].x;
                    }
                    else//ffrom y
                    {
                        k/=2;
                        x=e[i].y;
                    }
                }
            }
        }
        cout<<k<<"\n";
    }
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4556kb

input:

5 8 26
M 8 9 13
S 2 4 5
S 1 2 3
M 6 5 8
S 4 9 10
S 10 14 15
S 3 6 7
S 7 11 12
2 3
2 4
3 2
3 3
4 2
4 3
5 1
5 2
6 1
6 2
7 1
7 2
8 2
8 3
9 1
9 2
10 1
10 2
11 1
11 2
12 1
13 3
13 4
14 1
14 2
15 1

output:

5 
none
4 
none
none
none
none
none
2 
none
4 
none
none
none
none
none
none
none
4 
none
none
none
none
none
none
none

result:

wrong answer 5th lines differ - expected: '5', found: 'none'
English 繁體中文 简体中文

Server Time: 2024-12-05 05:58:26 | OpenSource Project