QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226425#7508. Fast DebuggerSolitaryDream#WA 186ms71580kbC++175.4kb2023-10-25 22:48:562023-10-25 22:48:57

Judging History

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

  • [2023-10-25 22:48:57]
  • 评测
  • 测评结果:WA
  • 用时:186ms
  • 内存:71580kb
  • [2023-10-25 22:48:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

using perm=vector<int>;

const int N=1e5+1e3+7,LIM=2e9;

int n,q;

int cnt;

perm operator *(const perm &a,const perm &b)
{
    perm ret(16);
    for(int i=0;i<16;i++)
        ret[i]=b[a[i]];
    return ret;
}

perm qpow(perm a,int b)
{
    perm ret(16);
    for(int i=0;i<16;i++)
        ret[i]=i;
    while(b)
    {
        if(b&1)
            ret=ret*a;
        b>>=1;
        a=a*a;
    }
    return ret;
}

int fa[N];

vector<int> g[N],pre[N];

vector<perm> pf[N][8];

int r[N],rep[N];

perm f[N][8];

int opt(string s,int x,int y)
{
    if(s[0]=='x')
        return x^y;
    if(s[0]=='a')
        return x&y;
    return x|y;
}

vector<int> dfs(int x)
{
    for(auto v:g[x])
    {
        if(r[v]>=LIM)
        {
            auto s=dfs(v);
            while(g[x].back()!=v)
                g[x].pop_back();
            g[x].pop_back();
            for(auto p:s)
                g[x].push_back(p);
            vector<int>().swap(g[v]);
            break;
        }
    }
    return g[x];
}

perm res[8];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    int x=0;
    rep[0]=1;
    for(int i=0;i<8;i++)
    {
        f[0][i].resize(16);
        for(int j=0;j<16;j++)
            f[0][i][j]=j;
    }
    for(int R=1;R<=n;R++)
    {
        string s;
        cin>>s;
        if(s=="repeat")
        {
            ++cnt;
            int y=cnt;
            cin>>rep[y];
            g[x].push_back(y);
            fa[y]=x;
            x=y;
            for(int i=0;i<8;i++)   
            { 
                f[x][i].resize(16);
                for(int j=0;j<16;j++)
                    f[x][i][j]=j;
            }
        }
        else if(s=="end")
        {
            int y=fa[x];
            r[y]=min(r[y]+r[x]*rep[x],LIM);
            for(int i=0;i<8;i++)
                f[y][i]=f[y][i]*qpow(f[x][i],rep[x]);
            x=y;
        }
        else if(s.back()=='i')
        {
            ++cnt;
            int y=cnt;
            fa[y]=x;
            g[x].push_back(y);
            r[x]++;
            r[x]=min(r[x],LIM);
            r[y]=1;
            rep[y]=1;
            string op1;
            int op2;
            cin>>op1>>op2;
            for(int t=0;t<8;t++)
            {
                f[y][t].resize(16);
                for(int i=0;i<16;i++)
                {
                    int o=i;
                    int j=op1[0]-'a';
                    int x=o>>j&1;
                    o^=(x<<j);
                    x=opt(s,x,op2>>t&1);
                    o^=(x<<j);
                    f[y][t][i]=o;
                }
            }
            for(int i=0;i<8;i++)
                f[x][i]=f[x][i]*f[y][i];
        }
        else
        {
            ++cnt;
            int y=cnt;
            fa[y]=x;
            g[x].push_back(y);
            r[x]++;
            r[x]=min(r[x],LIM);
            r[y]=1;
            rep[y]=1;
            string op1,op2;
            cin>>op1>>op2;
            for(int t=0;t<8;t++)
            {
                f[y][t].resize(16);
                for(int i=0;i<16;i++)
                {
                    int o=i;
                    int j1=op1[0]-'a';
                    int j2=op2[0]-'a';
                    int A=(o>>j1&1),B=(o>>j2&1);
                    o^=A<<j1;
                    A=opt(s,A,B);
                    o^=A<<j1;
                    f[y][t][i]=o;
                }
            }
            for(int i=0;i<8;i++)
                f[x][i]=f[x][i]*f[y][i];
        }
    }
    dfs(0);
    for(int i=0;i<n;i++)
    {
        if(!g[i].size())
            continue;
        pre[i].resize(g[i].size());
        for(int j=0;j<8;j++)
        {
            pf[i][j].resize(g[i].size());
            for(auto &x:pf[i][j])
            {
                x.resize(16);
                for(int t=0;t<16;t++)
                    x[t]=t;
            }
        }
        pre[i][0]=r[g[i][0]]*rep[g[i][0]];
        for(int j=0;j<8;j++)
            pf[i][j][0]=f[g[i][0]][j];
        for(int j=1;j<g[i].size();j++)
        {
            pre[i][j]=pre[i][j-1]+r[g[i][j]]*rep[g[i][j]];
            for(int t=0;t<8;t++)
                pf[i][t][j]=pf[i][t][j-1]*qpow(f[g[i][j]][t],rep[g[i][j]]);
        }
    }
    while(q--)
    {
        int k,v[4],nv[4]={0,0,0,0};
        cin>>k>>v[0]>>v[1]>>v[2]>>v[3];
        for(int i=0;i<8;i++)
        {
            res[i].resize(16);
            for(int j=0;j<16;j++)
                res[i][j]=j;
        }
        int x=0;
        while(k)
        {
            int t=k/pre[x].back();
            for(int i=0;i<8;i++)
                res[i]=res[i]*qpow(f[x][i],t);
            k%=pre[x].back();
            if(!k)
                break;
            int p=upper_bound(pre[x].begin(),pre[x].end(),k)-pre[x].begin();
            if(p)
            {
                for(int i=0;i<8;i++)
                    res[i]=res[i]*pf[x][i][p-1];
                k-=pre[x][p-1];
            }
            x=g[x][p];
        }
        for(int i=0;i<8;i++)
        {
            int o=0;
            for(int j=3;j>=0;j--)
                o=(o*2+(v[j]>>i&1));
            o=res[i][o];
            for(int j=0;j<4;j++)
                nv[j]+=(o>>j&1)<<i;
        }
        for(int i=0;i<4;i++)
            cout<<nv[i]<<" \n"[i+1==4];
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 48352kb

input:

6 2
repeat 5
xor ax bx
xori ax 3
and cx ax
xor cx dx
end
10 1 2 4 3
8 4 1 2 3

output:

0 2 2 3
4 1 3 3

result:

ok 8 numbers

Test #2:

score: -100
Wrong Answer
time: 186ms
memory: 71580kb

input:

11982 10000
repeat 2
repeat 2
andi bx 201
xori cx 241
repeat 4
xor cx bx
xor ax dx
repeat 8
or dx bx
xori dx 22
end
repeat 2
xor dx bx
xor dx bx
repeat 7
xor bx bx
or cx dx
and bx cx
end
andi dx 33
xori ax 179
xori bx 56
end
xori dx 63
xori cx 91
xori dx 228
or cx dx
repeat 6
xor cx dx
xori bx 198
x...

output:

24 195 0 75
0 195 0 245
199 193 6 13
252 73 245 67
0 0 0 0
51 0 0 245
113 52 121 214
51 195 0 75
247 253 247 37
119 198 119 186
235 235 44 36
4 0 181 0
76 228 253 0
51 245 245 33
119 119 176 0
198 198 1 11
199 93 154 3
106 106 152 21
93 92 42 3
236 236 247 147
198 198 204 135
0 51 0 75
119 118 10 15...

result:

wrong answer 25th numbers differ - expected: '99', found: '113'